Während ältere Forschungen eine Ersterwähnung im Jahr 1174 und eine Ableitung vom altsächsischen Begriff bom für Baum möglich hielten, lehnt dies die zeitgenössische Ortsnamenforschung ab. Sie geht von einer Ersterwähnung als Benem in einer päpstlichen Urkunde aus dem Jahr 1209 aus, in der dem Kloster Ringelheim Besitzungen und Privilegien bestätigt werden und favorisiert eine Ableitung von einem Personennamen Baio.
Archäologische Quellen erlauben einen Einblick in Zeiten, aus denen keine schriftlichen Quellen überliefert sind. Ein mehrere Jahrtausende altes Erdwerk aus der Jungsteinzeit hat bis heute aus der Luft zu erkennende Spuren auf einem Acker in der Gemarkung Beinum hinterlassen. Bei Wegebauarbeiten zwischen Beinum und Calbecht wurde in den 1880er Jahren eine römische Silbermünze gefunden, die das Porträt von Marc Aurel zeigt.
Das Amt Liebenburg, zu dem Beinum gehörte, ließ 1548 ein Erbregister erstellen, das Einblicke in die Verhältnisse vor Ort erlaubt: Beinum hatte zu jener Zeit 31 Hofstellen. Die insgesamt acht Ackerhöfe bewirtschafteten bis zu 120 Morgen Ackerland, Wiesen und Wald, während den 23 Kothöfen lediglich bis zu 25 Morgen Land zur Verfügung standen.
Zu Beginn des 19. Jahrhunderts wechselte die politische Zugehörigkeit von Beinum häufig. 1803 wurde das Hochstift Hildesheim aufgehoben und Beinum gehörte zunächst zu Preußen, das 1806 Napoleon unterlag und die Hälfte seines Territoriums verlor. Bis 1813 gehörte Beinum zum Königreich Westphalen, an dessen Spitze Jérôme, der jüngste Bruder Napoleons stand. 1815 wurde das Gebiet des ehemaligen Fürstbistums endgültig dem Königreich Hannover zugesprochen. Zum 1. April 1942 wurde das seit 1885 zum Landkreis Goslar gehörende Beinum Teil der neu gebildeten Stadt Watenstedt-Salzgitter.
Südlich von Beinum wurde im Frühjahr 1938 ein Lager errichtet, in dem zunächst rund 200 Arbeiter der umliegenden Erzschächte untergebracht waren. Im Sommer 1940 erfolgte die Umwandlung in ein Kriegsgefangenenlager, in dem bis zum Kriegsende sowjetische Kriegsgefangene interniert waren. Im November 1947 wurde das Lager aufgegeben und größtenteils abgerissen.
Heute leben in dem zur Ortschaft Südost gehörenden Stadtteil, der immer noch eher landwirtschaftlich geprägt ist und über eine gut funktionierende Dorfgemeinschaft und ein reges Vereinsleben verfügt, knapp 500 Menschen.