Der Name Maihingen kennzeichnet eine alemannische Anlage. Eine vorausgehende Besiedlung in der Römerzeit kann vermutet werden. Der Flurname »Rotes Tor« und ein bei Straßenbauarbeiten an der Römerstraße am südlichen Ortsrand gefundener Quader deuten darauf hin. Urkundlich wurde der Ort erstmals 1251 erwähnt. Eine wechselvolle Geschichte, Bauernkrieg, Dreißigjähriger Krieg und zwei große Brände (1717 und 1748) veränderten oftmals das Dorfbild.
In der unmittelbaren Nähe des Ortes befindet sich geologisch äußerst interessantes Gestein, dessen Ursprung auf den Meteoriteneinschlag vor ca. 15 Millionen Jahren (Entstehung des Rieskessels) zurückzuführen ist. Ein Besuch dieser Formationen war u. a. im Trainingsprogramm der Astronauten der Apollo 14 und Apollo 17 Missionen der NASA enthalten.