Durch das Gemeindegebiet von Nebelberg führte schon in früher Zeit ein Handelsweg (Schiffl, Schopper) von der Donau zur Moldau (Fund aus der Steinzeit in Vorderschiffl). Die Rodung und Besiedlung erfolgte durch die hochfreien Falkensteiner im 13. und 14. Jahrhundert. Nach 1300 kam das Gebiet an das passauische Landgericht Velden (=Neufelden).
Beim Bauernaufstand 1595 bis 1597 wurden bei Nebelberg Soldaten des Landrichters erschlagen. Im Erbfolgekrieg 1701 bis 1704 wurden an der Grenze Schanzen aufgeworfen. An die Franzosendurchzüge erinnert die Donabauerkapelle.
Nebelberg leitet seinen Namen vom Gründer der beiden Ortschaften Vorder- und Hinternebelberg, dem Grafen Eppo (Eberhard von Windberg) Formbach in Niederbayern ab. Eppo hatte im oberen Mühlviertel große Besitzungen. Er starb im Jahre 1110 kinderlos in St. Florian.
„Ich Otto der Piber vergich und tue kund allen den, die nun sint gegenbürtig und hernach chünftig sind und disen brief sehent oder lesen hörent, das…“
Mit diesen Worten im Vertrag vom 11. November 1296, verkaufte Otto der Piber dem Bischof Bernhart von Passau, beziehungsweise dem Kloster Engelszell sein Dorf zu „Eppenberg“ mit allem Zugehör (siehe dazu Oö. Urkundenbuch, Band VI; Seite 585). Der Name Eppenberg (= Nebelberg) entstammt vom Gründer der Ortschaft Nebelberg – Graf Eppo (=verkürzte Form für Eberhard) von Formbach. Dieses Adelsgeschlecht der Formbacher hatte im heutigen Österreich große Besitzungen und dürfte auch die ersten „Siedlungen“ in unserer Gegend angelegt haben.
Seitens der Gemeinde Nebelberg wurde man auf die geschichtliche Begebenheit im Zuge der Ausstellung zur Amtshauseröffnung aufmerksam. Bei dieser Ausstellung wurde eine Kurzchronik der Gemeinde Nebelberg präsentiert. Durch diese Nachforschungen stieß man auf das historische Ortslexikon (Lexikon des Landes Oberösterreich, 3 Bände – Erschienen in Linz 1935/40) des Herrn Konrad Schiffmann. Dieser hat in mühevoller Kleinarbeit dieses Verzeichnis angelegt, wobei darin auf die Urkunde vom 11.11.1296 verwiesen wird (Oö. Urkundenbuch).
Urkundlich wird Nebelberg erstmals 1296 genannt (Literatur: OÖ. Urkundenbuch, Band VI, Seite 585). 1467 wird erstmals vom vorderen Epelberg und vom hinteren Epelberg geschrieben (Literatur: Jahrbuch Mus. 1909, Seite 39). Weitere schriftliche Erwähnungen: 1537 Empmperg – Urbar zu Falkenstein, f. 50 und 53; 1581 Eppenberg – Urbar zu Rannariedl; 1787 Eberberg – Schutzkarte;
Nebelberg leitet seinen Namen vom Gründer der beiden Ortschaften Vorder- und Hinternebelberg, dem Grafen Eppo (Eberhard von Windberg) Formbach in Niederbayern ab. Eppo hatte im Oberen Mühlviertel große Besitzungen. Er starb im Jahre 1110 kinderlos in St. Florian. Es kann daher angenommen werden, dass Oepping und Teile der Ortschaften Vorder- und Hinternebelberg schon vor 1100 entstanden. In den Pfarrmatriken von Peilstein, die ab 1612 vorhanden sind, schrieb man die Ortsnamen noch annähernd richtig und es heißt da „in den vorderen oder in den hinteren Öppl- oder Epplberg“. Der Unverstand und die Gleichgültigkeit früherer Kanzleimenschen machte dann aus dem Epplberg einen Nebelberg.
Die Streusiedlung Heinrichsberg leitet ihren Namen von den Hörleinsbergern, die um 1370 zum ersten Mal im oberen Mühlviertel genannt wurden, ab. Sie stammten vom Herleinsbergerhof in der Pfarre Rohrbach. 1421 – 1503 besaßen sie pfandweise Tannberg und Peilstein. Bei Gründung der Pfarre Kollerschlag im Jahre 1786 wurde ein Teil von Heinrichsberg – wozu früher alle Häuser von Stift am Grenzbach rechts vom Stiftholz gehört haben – der Ortschaft Stift am Grenzbach einverleibt, sodass die beiden Ortschaften gleich viele Häuser hatten.
Die Gemeinde Nebelberg wurde, wie auch alle Nachbargemeinden nach der Bauernbefreiung im Jahre 1848 gegründet.
