Если более ранние исследования считали возможным первое упоминание в 1174 году и производное от древнесаксонского термина bom, означающего Baum, то современные исследования географических названий отвергают это. Они предполагают первое упоминание как Бенем в папском документе 1209 года, в котором подтверждаются владения и привилегии монастыря Рингельхайм, и отдают предпочтение производному от личного имени Байо.
Археологические источники дают представление о временах, от которых не сохранилось письменных источников. На одном из полей в районе Бейнум неолитическая земляная насыпь, датируемая несколькими тысячелетиями, оставила следы, которые до сих пор можно различить с воздуха. Во время строительства дороги между Бейнумом и Кальбехтом в 1880-х годах была найдена римская серебряная монета с портретом Марка Аврелия.
В 1548 году в Либенбурге, к которому относился Бейнум, был составлен реестр наследства, который дает представление о местных условиях: в Бейнуме в то время было 31 хозяйство. Восемь пахотных хозяйств обрабатывали до 120 акров пашни, лугов и леса, в то время как 23 навозных хозяйства имели в своем распоряжении всего 25 акров земли.
В начале XIX века политическая принадлежность Бейнума часто менялась. В 1803 году Хохстифт Хильдесхайм был упразднен, и Бейнум первоначально принадлежал Пруссии, которая в 1806 году пала перед Наполеоном и потеряла половину своей территории. До 1813 года Бейнум принадлежал Вестфальскому королевству, во главе которого стоял Жером, младший брат Наполеона. В 1815 году территория бывшего князя-епископства была окончательно передана Ганноверскому королевству. 1 апреля 1942 года Бейнум, который с 1885 года принадлежал району Гослар, стал частью новообразованного города Ватенштедт-Зальцгиттер.
Весной 1938 года к югу от Бейнума был построен лагерь, в котором первоначально проживало около 200 рабочих из близлежащих рудных шахт. Летом 1940 года он был преобразован в лагерь для военнопленных, где советские военнопленные содержались до конца войны. В ноябре 1947 года лагерь был заброшен и в основном снесен.
Сегодня в районе, который является частью деревни Зюдост, проживает чуть менее 500 человек, здесь по-прежнему развито сельское хозяйство, хорошо функционирует деревенская община и ведется активная клубная жизнь.