The first permanent English-speaking settlers came to the northeast portion of Alachua County in the 1820's. In 1837, during the Second Seminole War, an army post, Fort Harlee, was established on the Santa Fe River about three miles north of this spot. Abandoned as a military installation in 1838, the settlement at Fort Harlee served as a postal center for the surrounding community until 1858. In that year a post office was established at a town being founded at the point where the Florida Railroad (then under construction) would cross the Bellamy Road. This new town was named Waldo in honor of Dr. Benjamin Waldo. The name was probably selected by David Levy Yulee, president of the Florida Railroad. By February 1, 1859, the Florida Railroad was completed through Waldo to Gainesville. The Peninsular Railroad, planned as early as 1859 to run from Waldo to Tampa, was completed to Ocala in 1881. Both roads were part of the Florida Transit Railway. Waldo had become an important rail junction and continued to be until the shops and headquarters were moved beginning in 1929.
Another transportation link was established in 1879 when the Santa Fe Canal Company completed construction of two canals from Waldo to Melrose via Lake Alto and Lake Santa Fe. In the late 19th century the steamboat "F.S. Lewis" and later the "Alert" carried passengers and freight. Commercial use of the canals declined around 1920, but they continue to be used by pleasure craft. Waldo citizens met in 1876 and organized a municipal government. The town was incorporated August 1, 1907. Many settlers and tourists came to Waldo in the 1880's, reflecting the growth of the citrus industry in North Florida. The freezes of 1886 and 1894-95 ruined the citrus groves in the Waldo area, but the region has remained an agriculturally productive one.