The birthplace of present-day Leupp was Tolchaco, a missionary settlement founded by Mr. William Riley Johnston in 1900 located along the Little Colorado River. Briefly, Mr. W.R. Johnston arrived in 1896 at Moenkopi with his wife Margaret and his 4-year old son, Phillip to implement "The Work." As a Methodist missionary from Kansas, his job was to Christianize the Navajos of Tuba City. Since housing was not available for the family, they occupied a red stone building in Moenkopi, which earned him his Navajo name of "Kinlichíinii" or Red house. His son, Phillip was known as the Son of Redhouse or Kinlichíinii biye'. His wife served as a nurse to the Navajos and provided treatment for trachoma, injuries and childbirths. Three years later, they left Tuba City for not one Navajo was Christianized.
From February 1900 to 1912, Mr. W. R. Johnston began the missionary settlement at Tolchaco by the cottonwood grove about 10 miles north of present-day Leupp. For two years, the Johnston Family lived in a tent. By 1902, three cottages were built from cottonwood logs and one from salvaged materials of a Winona Saloon. In 1904, Mr. Maxwell, a federal agent lived in this same ex-saloon cottage. In addition to enforcing law and order, Mr. Maxwell looked for a more prominent place for a new community and found the site for the "Old Leupp" community.
Tolchaco initiated many beginnings for the Leupp community including the first post office, church services, a trading post, and the first school. In 1912, the Johnston family moved to Indian Wells to continue "The Work." In 1918, the huge adobe building burned down. Shortly after, the site was abandoned.