Die erste Besiedelung des Gebiets fand nachweislich bereits in der Altsteinzeit statt. Errichtung des „Leebergs“ (Tumulus/Hügelgrab) in der Hallstattzeit.
Niederhollabrunn gehört zu den ältesten Ansiedelungen und Pfarren links der Donau. Die Schreibweise des Ortes war ständigen Änderungen unterworfen. So kann man in Urkunden auch Holainbrunen, Holerinbrunen, Hollarenbrunnen, Holarbrunen, Nidern Holaprun, Nieder-Holebrunn finden.
Erste urkundliche Erwähnung im Jahre 1135:
Im Jahre 1135 entschloss sich Markgraf Leopold III., „a domno Reginmaro sancte Pataviense ecclesie episcopo sepe paterne admonitus, devote instructus, humiliter rogatus (M.B. XXVIII/2 Nr. 124. A. 93 f., und Fischer, Klosterneuburg, Nr. 4) zur Beendigung aller Streitigkeiten, die Zehenten von 13 Pfarren an den Bischof zu übergeben (remisit). Unter den 13 angeführten Pfarren ist auch die Pfarre Niederhollabrunn. Aus dem Besitz der babenbergischen Pfarren nach Eigenkirchenrecht erklärt sich der Besitz der Zehenten, die Gegenstand dieser Urkunde sind.
Als Quelle ersten Ranges für das Geschlecht der Edlen von Hollarinbrunnen ist das Saalbuch des Stiftes Klosterneuburg zu nennen, in dem im Laufe des 12. Jahrhunderts einige Mitglieder genannt werden: 1113 Adalramus de Hollarenprunnen, 1160 Sighard (als Zeuge einer Schenkung von Herzog Heinrich II. Jasomirgott) und 1171 Siglohus sowie sein Bruder Otto de Hollarbrunne. Dann dürfte dieses Geschlecht bald wieder erloschen sein.
Nach dem Geschlecht der „Edlen von Hollarinbrunnen“ wurden die Herren von Gerloß Eigentümer von Niederhollabrunn. Nach der Familie Gerloß kam der Ort an das Bistum Passau. Es ist bisher noch unklar, ob der Ort durch Kauf, Tausch oder Schenkung an das Bistum kam. 1222 war Bischof Gebhard von Passau vorübergehend genötigt, das Dorf an Herzog Leopold VI. als Lehen zur Abtragung eines Schuldenrestes zu übertragen.
1258 hatte auch das Chorherrenstift Klosterneuburg in Niederhollabrunn Besitz, welches dem ältesten erhaltenen Urbar von Klosterneuburg entnommen werden kann. 1177–1185 hatte Herzog Leopold V. dem Stift die Kinder des Gerung von Niederhollabrunn geschenkt. Das Stift Heiligenkreuz hatte Besitz laut einem Urbar vom Ende des 13. Jahrhunderts.
Darüber hinaus teilte der Ort natürlich auch die wechselvolle Geschichte Österreichs.
Nach dem niederösterreichischen Gültenbuch kam die Herrschaft Niederhollabrunn im Jahre 1810 an den k. u. k. Cameralfond; im Jahre 1813 im Namen desselben an die k.u.k. Staatsgüter-Administration. Im selben Jahr kam dieser Ort dann durch Kauf an Hauptmann von Säulen, 1815 an Anton und Anna Maria Girsch und 1819 an Joseph Ritter von Schreibers. Dieser wird in der „Darstellung des Erzherzogtums Österreich unter der Enns“, 3. Band, Ort Niederhollabrunn, erwähnt. Aus diesem Buch ist eine recht genaue Beschreibung der Gemeinde Niederhollabrunn zu entnehmen. Zu dieser Zeit hatte sie 126 Häuser und war ein Rastplatz mit der nächsten Poststation Stockerau. Der Ort zählte 1834 145 Familien mit 110 schulpflichtigen Kindern, 55 Pferde, 157 Kühe, 238 Schafe, 16 Ziegen, 250 Schweine, 138 Joch Ackerland und 118 Viertel Weingärten.
Im Jahre 1919 ging das Schloß samt Grundbesitz und Wirtschaftsgebäude aus dem Besitz des Grafen Dubsky an die Dienerinnen vom heiligsten Herzen Jesu, Wien, 3. Bezirk, über. Diese errichteten 1920 in den Wirtschaftsgebäuden den Kindergarten.
Das ehemalige Kloster ging im Jahr 2003 in Privatbesitz über. Der Kindergarten ist nach wie vor im ehemaligen Wirtschaftsgebäude untergebracht und wird als 2-gruppiger Landeskindergarten geführt.
Der Ortskanal (Regenwasserkanal) von Niederhollabrunn wurde im Jahr 1978 begonnen, die Gehsteige und die Ortsstraße 1980 hergestellt.
Die Freiwillige Feuerwehr Niederhollabrunn wurde 1885 gegründet. Hauptmann war damals Wilhelm Rapolt, sein Stellvertreter war Johann Wagner.
In den Jahren von 1780 bis 1821 war die Volksschule Niederhollabrunn in einem umgebauten Speicher des Hauses Nr. 1 untergebracht. 1822 wurde das Gebäude aufgestockt und mit einem Ziegeldach versehen. Mit Beginn des Schuljahres 1972/73 harte das Bestehen der Volksschule Niederhollabrunn auf, die Kinder besuchen seither die Volksschule in Bruderndorf. Um die Form einer vierklassigen Schule aber zu wahren, wurde mit der Volksschule Leitzersdorf ein Schulverband geschlossen. Heute ist das ehemalige Schulgebäude im Privatbesitz und trägt die Adresse Kirchenplatz 3.
Als erster Bürgermeister ist Herr Georg Penner (1865-1873) bekannt.
Die Katastralgemeinde Niederhollabrunn erstreckt sich über 1104,9717 ha, davon sind ca. 253 ha mit Wald bedeckt.