История Гаммельстада начинается примерно с XIII века. Тогда он назывался Лулео и был важным местом торговли между Финляндией и Стокгольмом. В XIII веке Гаммельсад был маленьким поселением, расположенном на острове. В 1621 году он был объявлен городом, но в 1649 году был перенесён на настоящее местоположение Лулео из-за поднятия земной коры. На протяжении более 100 лет оба места развивались параллельно.
Гаммелстад является одним из многих существовавших ранее в Швеции церковных городков. Церковный городок был центром обширного прихода. Из-за низкой плотности населения, которое в средние века не превышало 2000 человек и больших расстояний между деревнями, относившимся к одному приходу, прихожане не успевали за один день сходить в церковь и вернуться домой. Поэтому вокруг церквей стали строить избушки, в которых могли переночевать пришедшие издалека прихожание. Так возникли церковные городки. Традиционно избушки были очень простые. Они остаются простыми и по сей день, в них есть электричество, но нет канализации и центрального отопления. Почти все избушки принадлежать частным лицам.