The land on which Lincoln Park stands was a cemetery in use in the late 1860s and possibly earlier. In 1902, golf enthusiasts laid out a three-hole course on part of the land. In 1909, the Board of Supervisors turned the land over to the Parks Commission, and cemetery relocation began. The golf course expanded to 14 holes by 1914, then to a full 18 holes in 1917. During this period of development some 50 acres (200,000 m2) of the original tract were turned over to the federal government to be added to the neighboring Fort Miley Military Reservation.
The Lincoln Highway, with its western terminus at Lincoln Park, was conceived and mapped in 1913 as the first coast-to-coast road across America, traversing 14 states. The original western terminus marker of the highway was located at the north end of the plaza and fountain in front of the Legion of Honor. Today, a replica of the western terminus marker and an interpretive plaque are located at the southwest corner of the plaza, next to the bus stop. The replica marker was placed in 2002 during the revitalized Lincoln Highway Association's 10th Annual National Convention by the Association's California Chapter.