The area covered by today's Houston County was first organized as St. Croix County, of the Wisconsin Territory, in 1839. On October 27, 1849, part of that county was partitioned off to create Wabashaw County of the Minnesota Territory. On February 23, 1854, the territorial legislature authorized the partitioning of sections of Wabashaw to create Fillmore County and Houston County. An election on April 4, 1854, allowed the county government to be completed. The county was named for Sam Houston, who had been president of the Republic of Texas and a US senator from Texas. The village of Houston was the first county seat. Then a land speculator made an effort to move the seat to Caledonia, and in 1855 the county board moved the county records to Caledonia, which became the de facto seat, and eventually the legal seat after several county votes. In 1855 the records were stored in the cabin of Commissioner Samuel McPhail; the first court hearings were held in that cabin, and a one-story courthouse and jail was built in Caledonia in 1857. A two-story building was built in Caledonia in 1867, and several referendums made Caledonia the county seat by 1874. From that point on, Caledonia prospered and Houston slowly declined. The only other area of prominence was La Crescent, which benefited from its connection to La Crosse, Wisconsin.