Apple Valley's historical roots lead back to the mid-1800s when it was a farming community known as Lebanon Township. The first settlers to the area were believed to have come from the east coast around 1855. On April 6, 1858, the Dakota County Board of Commissioners created Union Township. The board met again on April 26, 1858, and changed the boundaries of Union Township, creating Lebanon Township from a portion of the former Union Township.
The first town meeting was held on May 11, 1858, in a home near the area that is now Westview Elementary School. Lebanon Township remained much the same for its first century. The town's population in 1881 was 252 and in 1960 was 585.
The township began to transform in the mid-1950s. Residential neighborhoods began to develop in the spring of 1955. A Planning Commission was established in 1962. In 1963, Orrin Thompson began building in the area. Thompson selected the name Apple Valley for several of his plats on either side of County Road 42 that were located in the southwest corner of the city. Thompson had an apple tree planted at each home in some of the new developments. In 1966, a volunteer fire department was organized. In the general election of 1968, the residents voted to incorporate the Town of Lebanon as the Village of Apple Valley. A mayor and four councilmembers were elected and took office on January 1, 1969. On January 1, 1974, Apple Valley became a statutory city.