Well, way back in TA 1100 it says:
The Wise ( the Istari and the chief Eldar ) discover that an evil power has made a stronghold at Dol Guldur. It is thought to be one of the Nazgul.
This is later known to be Sauron, who "retreats and hides in the East" in 2063, only to return in 2460.
( Also, several Nazgul are sent to reoccupy Dol Guldur when Sauron "declares himself openly" in Mordor in 2951. )