Arholzen entstand im sächsischen Gau Engern, dem Siedlungsgebiet der Cherusker. Die Gründung des Dorfes wird vor 800, in der sogenannten zweiten Siedlungsperiode zwischen 500 und 900 vermutet. Damals entstanden Ortschaften, deren Namen z.B. auf -hausen (verkürzt oft zu sen) enden. Die erste urkundliche Erwähnung des Dorfes finden wir in einer an das Kloster Corvey gerichteten Schenkung (nicht datiert, jedoch zwischen 891 und 1037 entstanden) auf. Hier in Adololdeshusen erhielt das Kloster 30 Morgen und einen Acker. 1150 wird die Gemeinde als Odololdeshem als hildesheimisches Lehen, zur Herrschaft Homburg gehörig, erwähnt. Damals übertrug Graf Hermann von Winzenburg das castrum (Burg) Homburg der Kirche zu Hildesheim zu ewigem Eigentum, um es als Lehen zurück zu empfangen. Die hier zugrundeliegende Urkunde vom 8.Mai 1150 ist das erste genau datierte Zeugnis über das Bestehen Arholzens.

1493 lag Arholzen wüst; d.h. es war von seinen Einwohnern verlassen worden. Sie mögen sich in den umliegenden Dörfern oder dem schutzgebenden Stadtoldendorf neu angesiedelt haben. Doch bereits wenige Jahrzehnte später wurde Arholzen unter Herzog Heinrich dem Jüngeren (1514-1568) wieder neu besiedelt. 1618 brach der Dreißigjährige Krieg aus. Die ersten Jahre waren für diese Gegend noch friedlich. Im Juli 1623 erschien der kaiserliche Feldherr Tilly bei Höxter an der Weser. Die erste Heimsuchung begann für das Weserbergland: das Kloster Amelungsborn wurde ausgeraubt, Stadtoldendorf belagert und eingenommen und das Land ringsrum verwüstet.

Dass dabei auch Arholzen und seine Einwohnerschaft nicht verschont blieb, ist gewiss, zumal im Jahr 1626 Arholzen infolge der Durchmärsche und Plünderungen ein Schaden von 905 Talern beklagte. Siebenmal zogen feindliche Kriegsscharen durch diese Gegend. Es waren furchtbare Not- und Elendsjahre. Das Volk verarmte. Während des Krieges hatte die Wolfplage zugenommen. Die Wölfe drangen am lichten Tage in die Häuser. Die Pest herrschte im Lande. Ihretwegen konnte 1658 der Pastor (wohnhaft in Stadtoldendorf) lange Zeit keinen Predigtgottesdienst in Arholzen halten. Die ersten Einwohnerzahlen liegen aus dem Jahr 1663 vor. Arholzen hatte damals 94 Einwohner, die Kinder unter 14 Jahren nicht mitgezählt. 1793 waren es 393 Personen, 1905: 617 und im Jahre 2000 betrug die Einwohnerzahl 484.

Von 1807 bis 1813 war das Herzogtum Braunschweig ein Teil des Königreiches Westfalen unter Jerome Napoleon. Arholzen gehörte zum Canton Stadtoldendorf im Distrikt Einbeck, im Departement Leine. Die alte Ämteraufteilung hatte damit ihr Ende erreicht. Seit dem Jahre 1832 bestand die Gliederung des Landes Braunschweig in 6 Kreise als Verwaltungsbezirke. Arholzen gehört seitdem zum Kreis Holzminden und seit 1879, nach Einteilung in vier Amtsgerichtsbezirke, zum Amtsgerichtsbezirk Stadtoldendorf.

Während des letzten Krieges, am 01.08.1941, gelangte Arholzen mit dem Kreis Holzminden im Austausch gegen den Kreis Goslar an die Provinz Hannover. Die Gemeinde trat Anfang der 1970‘iger Jahre erfolgreich für ihre Selbständigkeit ein und ist seit dem 01.01.1973 Mitglied der Samtgemeinde Stadtoldendorf.