Built by the Elves of Lindon at the beginning of the Second Age, it was afterwards used by Elves of any tribe (whether Noldor, Sindar, or Silvan Elf) to leave Middle-earth for Valinor. Círdan the Shipwright was Lord of the Havens, but throughout the Second Age Ereinion Gil-galad, High King of the Noldor, ruled all of Lindon from the Grey Havens.
Following the defeat of Sauron and the crowning of King Aragorn Elessar, Gandalf, Elrond, and Galadriel left Middle-earth for Valinor from the Grey Havens. They were accompanied by Bilbo and Frodo Baggins, who were given the honor of taking the Straight Road because they had both been a Ring-bearer. Years later, Fairbairn family tradition held that Sam Gamgee also sailed West from the Grey Havens because he too had been a Ring-bearer, even if just briefly.
It is unclear how long the Grey Havens lasted into the Fourth Age, as the number of Elves dwindled with the coming of the "Age of Men". Supposedly Círdan remained at the Havens until the last ship left from Middle-earth for the Blessed Realm.