In The Fellowship of the Ring, Book Two, III The Ring Goes South, there is an eerie passage when Aragorn guides the fellowship from Hollin (Eregion) to the mountain Caradhras:
It was the cold chill hour before the first stir of dawn, and the moon was low. Frodo looked up at the sky. Suddenly he saw or felt a shadow pass over the high stars, as if for a moment they faded and then flashed out again. He shivered. ‘Did you see anything pass over?’ he whispered to Gandalf, who was just ahead. ‘No, but I felt it, whatever it was,’ he answered. ‘It may be nothing, only a wisp of thin cloud.’ ‘It was moving fast then,’ muttered Aragorn, ‘and not with the wind.’
What was this shadow?
Apparently, this shadow was not caused by the crebain (regiments of black crows from Dunland and Fangorn Forest), which appeared on the previous day and which were clearly recognized by Aragorn.
It could have been a fell beast or even a Nazgûl riding on a fell beast. However, later in The Two Towers, Book Three, III The Uruk-hai, we learn from Grishnákh that the fell beasts were not supposed to cross the Anduin yet:
‘Nazgûl, Nazgûl,’ said Grishnákh, shivering and licking his lips, as if the word had a foul taste that he savoured painfully. ‘You speak of what is deep beyond the reach of your muddy dreams, Uglúk,’ he said. ‘Nazgûl! Ah! All that they make out! One day you'll wish that you had not said that. Ape!’ he snarled fiercely. ‘You ought to know that they’re the apple of the Great Eye. But the winged Nazgûl: not yet, not yet. He won’t let them show themselves across the Great River yet, not too soon. They’re for the War – and other purposes.’
This goes well with a description in Unfinished Tales, Part Three: The Third Age, IV The Hunt For The Ring, (i) Of the Journey of the Black Riders according to the account that Gandalf gave to Frodo:
(…) But Sauron did not underesteem the powers and vigilance of the Wise, and the Nazgûl were commanded to act as secretly as they could. (…)
The Lord of Morgul therefore led his companions over Anduin, unclad and unmounted, and invisible to eyes, and yet a terror to all living things that they passed. (…)
And indeed, the first encounter of the fellowship with a winged Nazgûl that is described in detail in The Fellowship of the Ring, Book Two, IX The Great River, occurs on the east-bank of the Anduin.