Als im Sommer 1999 die Erdarbeiten im Neubaugebiet "Am Lagerweg" begannen, entdeckte man unter einer bis zu einen Meter hohen Erdschicht Teile von Tongefäßen und Messerklingen. Diese Fundstücke lassen auf eine kontinuierliche Besiedlung der Holdorfer Gegend seit dem 8. Jahrhundert n. Chr. schließen.

Im Jahre 1188 wurde der Name Holthorpe - also das heutige Holdorf - erstmals vom Osnabrücker Domprobst Lentfried urkundlich erwähnt.
Während des 30-jährigen Krieges von 1618-1648 kam es auch in Holdorf zu Plünderungen und Verwüstungen. Diejenigen, die den Krieg überlebt hatten, kämpften in der Folgezeit mit den Kriegsfolgen: Viele Menschen hungerten aufgrund zerstörter Felder und Ernten, Pest und andere Seuchen griffen um sich.
Auch in der Folgezeit kam Holdorf nicht zur Ruhe: Die Holdorfer Gegend war entweder mit dem Landesfürsten in Oldenburg, dem Bischof von Osnabrück oder dem von Münster vebunden.

Im 19. Jahrhundert wurde Holdorf - wie ganze der südoldenburger Raum - von einer dramatischen Auswanderungswelle in Richtung  USA erfaßt. Die Gemeinde - zu Beginn dieses Jahrhunderts selbstständig geworden - verlor über 33 % seiner Einwohner von 1825 (ca.2300 Einw.) bis 1890 (ca. 1500 Einw.).
Von  Mai 1987 bis Juni 1997 ist die Bevölkerung von Holdorf um 21,6 % angewachsen (zum Vgl.: LK Vechta 19% , Land Nds. 9,4%) und hat mittlerweile die 6000 überschritten.