År 1613 utfärdade hertig Johan av Östergötland ett privilegiebrev för att locka utländska hantverkare och handelsmän till Norrköping. Förutom en rad ekonomiska förmåner skulle de – tillsammans med de tyskar som redan bodde i staden – få bilda en egen församling och bygga en kyrka.
Inflyttningen gick till en början trögt och 1618 bodde endast cirka 30 utlandsfödda familjefäder i staden. De flesta var från Tyskland, men vid vapenfaktoriet fanns också en handfull fransktalande hantverkare. Underlaget för en egen församling och kyrkbygge var alltså svagt och därtill rådde ekonomiskt svåra tider.
Sedan Louis De Geer flyttat till Norrköping 1627 växte den tyska befolkningen genom att han anlitade hantverkare från kontinenten till både faktoriet och mässingsbruket. De Geer anställde en präst för sin tysktalande personal: magister Christian Farther från Thüringen höll 1631 den första predikan på tyska i Norrköping. Gudstjänsterna firades i S:t Johannes kyrka och i Louis De Geers palats på Saltängen.
Vid 1640-talets mitt fanns det minst 150 invandrarfamiljer i staden. Majoriteten var antingen från Tyskland eller förstod tyska, till exempel de många holländarna på Holmens bruk.
År 1660 uppvaktade de tyska borgarna drottning Kristina för att få bilda en församling och bygga en kyrka. Kristina beviljade detta och utfärdade privilegier som även omfattade rätten till en tysk skola. Den tyska församlingens förste kyrkoherde blev Andreas Hammerhelf som var född i Nyköping.
Stadens mest förmögna handelsmän och industrichefer hade tyskt påbrå och att de anslöt sig till den nya församlingen gav finansiell styrka. Bänklängderna från 1680-talet visar att mellan 125 och 150 hushåll hörde till Tyska församlingen, vilket motsvarade ungefär 500–600 personer.
Kronan donerade Stenhusbacken, där Norrköpingshus hade legat, till församlingen 1663. Kyrkan uppfördes förmodligen på det nedbrunna slottets grundmurar. I april 1670 hölls en grundläggningshögtid då landshövding Anders Lilliehöök murade in en dokumentsamling på den plats där altaret skulle uppföras.
Det var fortfarande inte bestämt vad kyrkan skulle heta. Ett tidigt förslag var att namnge den efter aposteln Andreas, men församlingen valde i stället att uppvakta änkedrottning Hedvig Eleonora som gav tillstånd att använda hennes namn.
Tre år senare var det dags för högtidlig invigning på alla helgons dag den 1 november 1673. Den förrättades av Linköpingsbiskopen Johannes Terserus i närvaro av kung Karl XI och Hedvig Eleonora samt flera riksråd och andra prominenta gäster. På juldagen samma år började gudstjänsterna hållas i den nya kyrkan.
Vid invigningen var dock Hedvigs kyrka långt ifrån färdig – det saknades torn, sakristia, predikstol och orgel. Den ekonomiska krisen i Norrköping under 1670-talet hade även drabbat den tyska församlingen.
År 1678 anlades kyrkogården runt kyrkan och på 1680-talet byggdes en prästgård. År 1693 kom äntligen tornbygget igång.
När ryssarna anföll Norrköping 1719 plundrades och brändes stadens tre kyrkor. Den tyska kyrkan fick betydande skador på framför allt taket och tornet. Efter två år kunde man åter fira gudstjänst i den nödtorftigt reparerade kyrkobyggnaden, men inte förrän 1752 var alla restaureringsarbeten klara. Prästgården flyttades hit från en annan plats i staden 1782 och var en gåva av bruksägaren Christian Eberstein.
Församlingsmedlemmarna blev med tiden alltmer integrerade i Sverige och från 1775 fanns både en tysk och en svensk kyrkoherde som under ett par decennier växlade mellan tysk högmässa och svensk aftonsång och vice versa.
Men församlingen krympte och vid slutet av århundradet klagades över den dåliga uppslutningen på gudstjänsterna. Den siste tysktalande kyrkoherden, Johann Anton August Lüdeke, flyttade 1808 och sex år senare hölls för sista gången gudstjänst på tyska.
Församlingen var därefter en helt svensk församling och genom en uppdelning av S:t Olai församling 1885 blev Hedvigs församling en del av Svenska kyrkans församlingsstruktur.
Kyrkans inventarier speglar dess långa historia. Dopfunten är från år 1590-talet och kommer från Stegeborgs slottskapell. Predikstolen donerades till församlingen 1727 efter rysshärjningarna. Altartavlan målades 1791 av Pehr Hörberg. De båda korfönstren sattes in vid en renovering 1890 och ljuskronorna är sentida kopior av de gamla kronorna som såldes 1824.