Settlement in Mendon began in 1857 when Alexander Brice Hill, his wife Eliza Jane Wimmer, and his brother Robert Brice Hill acquired land and built a log cabin north of Maughan's Fort (Wellsville), the first Mormon community in Cache Valley. At that time Mendon was called North Settlement because of its location in relation to Maughan's Fort. Permanent occupation of Mendon did not begin until May 1859, when eight families arrived. (In 1858, Cache Valley settlers evacuated their homes prior to the arrival of the U.S. Army.)

In the winter of 1859-1860 Mendon had to be made into a temporary fort while territorial surveyor Jesse Williams Fox platted all of Cache Valley. Extensive developments began after the survey was finished as a number of additional settlers came to Mendon in the spring of 1860. By October 1863, after county surveyor James H. Martineau conducted another survey, the city had nine square blocks along with a central public square.

On April 1, 1870, the Legislative Assembly of Utah officially incorporated Mendon. George W. Baker served as the first mayor, along with six councilors, two justices and one town marshal. The 1870 census reported 427 residents, made up of 168 adults and 259 minors. By 1890, new homesteaders were not allowed in Mendon due to scarcity of water, although this ban did not remain in effect as the settlement continued into the early years of the 20th Century.