Około 1230 roku rozpoczęto budowę dzisiejszego kościoła w stylu gotyckim na miejscu kościoła poprzednio zniszczonego. Prace budowlane trwały przez dziesięciolecia XIII wieku. Dopiero w 1300 roku kościół został poświęcony św. Szczepanowi, który jest między innymi także patronem handlowców. W wyniku zmian budowlanych w ciągu lat budynek otrzymał obok fragmentów gotyckich i romańskich także wewnętrzne wyposażenie w stylu renesansowym i barokowym. W XV wieku wzniesiono westwerk z charakterystycznymi wieżami, które nie wystają ponad dach kościoła.
Pierwsze ewangelickie kazanie według nauki Lutra w kościele Sankt-Stephani-Kirche wygłosił już w 1530 roku pastor Heinrich Wende, który krótki czas później został wypędzony z miasta przez książęcego pana krajuHans-Erhard Müller: Helmstedt - die Geschichte einer deutschen Stadt. 2 wydanie 2004, strona 105.. Wraz z ostatecznym wprowadzeniem Reformacji w 1568 roku na obszarze księstwa Brunszwik-Lüneburg przez księcia Juliusza także opaci sąsiedniego katolickiego klasztoru Sankt Ludgeri stracili panowanie nad zborem przy kościele św. Szczepana, którzy do tej pory posiadali prawo obsadzania proboszcza.