The Nazgūl on their search for the OneRing were riding on black horses, until their Horses were destroyed by the flood at the Ford of Bruinen.
Tolkien gives several conflicting accounts of the journey of the Black Riders from Osgiliath to the Shire, but the following is certain:
- The Nazgūl and six of his companions passed unclad through Anorien and across northern Rohan to Sarn Gebir, where they collected their horses and cloaks.
- They then travelled north to the Field of Celebrant, where they met the remaining two Black Riders, Khamūl (who dwelt in DolGuldur) and his messenger.
- Using the information provided by Gollum during his torture, they then travelled north in search of the land of the Halflings, which they believed was located in the Gladden Fields (the old home of the Stoors). In one version of the tale, the Riders found a remnant of the Stoors here, and either killed them or drove them off.
- Foiled in the Vale of Anduin, the Riders then raced south to Isengard, where they had words with Saruman. This was at the time of Gandalf's escape, or shortly after. According to which version of the tale is more likely, they learned of the location of the Shire from Saruman or Wormtongue.
- The Riders then sped north along the North-SouthRoad into Eriador. In one version of the story, they overtook an agent of Saruman, and obtained from him detailed charts of the Shire. They then sent him to Bree to spy for Sauron. He was the "squint-eyed Southerner".
- According to one version of the tale, the Riders were not certain whether the Ring was in the Shire. Where the road to the Shire branched off from the main highway, the Nazgūl Lord sent the Riders to Sarn Ford, while he himself continued north along the Greenway, establishing a camp at Andrath, south of Bree.
- At Sarn Ford, the Riders were challenged by the Rangers, and the ford was held against them; but in the morning they broke through. Four entered the Shire before dawn on the 23rd September, 3018. The rest pursued the Rangers eastward, and then moved north to keep watch on the Greenway. At nightfall, Khamūl reached Hobbiton and interviewed Hamfast Gamgee. The following day, he almost caught up with Frodo, Sam and Pippin. On the 25th, he reached Bamfurlong and spoke with Farmer Maggott; that evening, Riders detected the hobbits at Bucklebury Ferry.
- Between the 23rd and the 29th, at least four of the Riders combed the Greenway and the Bree-land for the hobbits. During the night on the 29th, two Riders entered Bree, visiting Bill Ferny and Harry Goatleaf; they almost captured Merry. In the early hours of the 30th, they attacked the Inn, while the four Riders in the Shire invaded Crickhollow. Foiled on both counts, the Riders returned to their Captain at Andrath with news.