Fund aus der Keltenzeit
Das Dorf kann auf eine lange, ureigene Geschichte zurückblicken. In einem Keltengrab des 2 Jahrhunderts vor Christus wurde ein Bronzebeil entdeckt. 926 nach Christus - als Oberschwaben durch die Hunnen verwüstet wurde - besaß hier das Kloster Weißenburg/Unterelsass eine Anzahl von Höfen. Ebenso früh dürfte das spätestens im 15. Jahrhundert abgegangene, südlich von Oberholzheim gelegene Sallheim angelegt worden sein, dessen Wirtschaftsland teilweise von ihm übernommen wurde. Die Namen Alheim/Sallheim/Sallen erinnern noch heute daran. Das Apostelfürstenpatronat weist sogar auf ein vielleicht schon um die Jahrtausendwende bestehendes Gotteshaus hin. Seit 1275 ist "Holtzheim" eine selbständige Pfarrei, in der um die Mitte des 14. Jahrhunderts die Herren von Freyberg als Herrschaft ein gewichtiges Wort mitzureden hatten.
Die Oberhoheit war seit 1434/37 geteilt zwischen der Zisterzienserinnenabtei Gutenzell (Vorbesitzer waren auch Ulmer Bürger, u. a. die Reiter, Besserer und Raiser) und die Ulmer Patrizier- und Kaufmannsfamilien, so die Umgelter und Roth, die ihre Rechte 1439 ans Spital Biberach verkauften. Die Holzmühle ist erstmals 1449 erwähnt. Es handelte sich wohl stets um eine Mahlmühle. Sie wurde um 1685/89 neu erbaut. Schließlich zu einem Drittel gutenzellisch und zwei Dritteln spitalbiberachisch, führte die Reichsstadt 1536 die Reformation durch. Daraufhin übereigneten ihr 1544 die Herren von Stein zu Hürbel das Patronatsrecht über die nun evangelische Kirche Sankt Peter (und Paul), deren Baulast aber weiterhin bei Gutenzell lag. Spital Biberach und Kloster Gutenzell blieben bis 1803 gemeinsame Dorfherren. Nachweisbar erst in der Neuzeit galt - entsprechend dem Umfang des beiderseitigen Grundbesitzes - die Teilung der Ortsherrschaft in zwei Drittel des Spitals und ein Drittel des Klosters.
Durch den Reichsdeputationshauptschluss 1803 kam der spitälische Teil an Baden, der gutenzellische an die Grafen von Toerring-Gutenzell. Nachdem beide Teile 1806 württembergisch geworden waren, bildete das Dorf ein Kondominat (eine Doppelherrschaft) zwischen dem Oberamt Biberach, dem der spitälische Teil direkt unterstand, und dem Obervogteiamt Gutenzell des Oberamts Waldsee. Nach Aufhebung des Obervogteiamts 1809 und der kurzen Zugehörigkeit des gutenzellischen Teils zum neuerrichteten Oberamt Ochsenhausen kam das Dorf 1810 ungeteilt zum Oberamt Wiblingen (mit dem bis 1826 bestehenden Unteramt Laupheim). Seit 4. August 1845 war Oberholzheim dem neu gebildeten Oberamt Laupheim angehörig. Mit der Aufhebung des Oberamts Laupheim kam es dann am 1. Oktober 1938 zum Landkreis Biberach.
