Vanhin maininta kirkollisesta toiminnasta Torniossa on 1300 - luvun alusta. Silloin Upsalan piispa Hemminki vieraili täällä kastaen lappalaisia sekä karjalaisia suuressa vesiammeessa. Tornio sai kaupunkioikeudet 1621, ja sen ensimmäinen kirkko vihittiin 1647. Salaman sytyttämä tulipalo tuhosi kuitenkin tämän kirkon heinäkuussa 1682. Sieltä saatiin pelastetuksi vain hopeinen kannu ja öylättiastia sekä veistos, joka kuvaa Jeesusta ristillä, Mariaa sekä Maria Magdaleenaa. Veistos on nykyisen kirkon sakaristossa.
Nykyistä, kaupungin toista kirkkoa ryhdyttiin rakentamaan keväällä 1684 paikalle, joka sijaitsee entisestä kirkosta pari sataa metriä koilliseen. Kirkko vihittiin heinäkuun 11. Päivänä 1686, ja se sai silloisen Ruotsin kuningattaren mukaan nimekseen Hedvig Eleonoran kirkko. Länsipuolella oleva kellotapuli rakennettiin vuosina 1686 - 1687. Se on vanhin säilynyt pohjalainen tapuli.
Sekä kirkon että tapulin suunnittelija ja rakennusmestari oli liminkalainen talonpoika Matti Härmä. Hänen isänsä Jooseppi Härmä oli myös tunnettu kirkonrakentaja Pohjois - Savossa. Rakennusteknillisesti Tornion kirkko muistuttaa monia Pohjanmaan puukirkkoja. Mallina Matti Härmällä oli ollut keskiaikainen suomalainen harmaakivikirkko. Sen mukaan hän on jakanut katon neljään holvikupuun. Kaksi näistä kattoholveista on koristettu arvokkailla maalauksilla. Kirkko on suorakaiteen muotoinen. Pohjoissivulla oleva sakaristo ja eteläsivulla oleva asehuone tekevät kirkosta ristinmuotoisen. Keskiholvin koristeaiheiset maalaukset ovat vuodelta 1687. Ne kustansi raatimies Henrikki Eerikinpoika, joka nukkuu viimeistä untaan kirkon lattian alla olevassa perhehaudassa. Seuraavana vuonna Alatornion kuulu kirkkoherra Gabriel Tuderus lahjoitti yhdessä vaimonsa kanssa kuoriholvin kauniit öljyvärimaalaukset. Ne esittävät Vanhan ja Uuden Testamentin tapahtumia ja henkilöitä. Viimeinen tutkimus pitää niiden maalaajana oululaista Lars Galleniusta. Penkkien ovien maalaukset ovat vuodelta 1748 ja niistä vastasi Erik Fellström. Molempien holvimaalausten värit ovat säilyneet hämmästyttävän hyvin. Se johtunee siitä, että värit valmistettiin tuohon aikaan luonnontuotteista. Esimerkiksi punainen väri on saatu sekoittamalla häränverta ja kananmunia. Kattomaalaukset on tosin entisöity vuonna 1912.
Alttarin erottaa muusta kirkosta kuoriaitaus. Tämän kuoriaitauksen, samoin kuin saarnastuolinkin ympäristöineen on veistänyt torniolainen puuseppä Niilo Jaakonpoika Fluur. Tyyliltään veistokset ovat myöhäisrenessanssia ja alkavaa barokkia. Kaikki nämä veistostyöt on maalannut tanskalainen taidemaalari Didrik Möllerum. Hän on myös maalannut asehuoneen oven yläpuolella olevan kirkon vanhimman, ehtoollista esittävän alttaritaulun vuonna 1701. Nykyisen alttaritaulun "Jeesus Getsemanessa" on maalannut taidemaalari Ollongren vuonna 1754.
Alttariseinän vasemalla puolella on musta muistotaulu kuningas Kaarle XI:n käynnistä Torniossa vuonna 1694. Kuningas tuli tuolloin katsomaan keskiyön aurinkoa kellotapulista. Toinen taulu on muistokirjoitus seurakunnan ensimmäisestä kappalaisesta Martinus Kempestä. Alttarin oikealla puolella on Lapin kirkkojen ainoa aatelisvaakuna. Se on Torniossa vuonna 1694 kuolleen majuri Aleksander Ferdinand von Sackenin, Länsi-Pohjan rykmentin komentajan hautausvaakuna. Hänet on haudattu kirkon lattian alle, kuten monet torniolaisetkin. Useat vainajat ovat muumioituneet ja säilyneet erittäin hyvin. Vuoden 1818 jälkeen ei kirkkoon ole saanut enää haudata.
Monet seurakuntalaiset ovat tehneet kirkolle lahjoituksen jonkun merkittävän tapauksen tai omaisensa muistoksi. Kaikki 14 messinkistä kynttiläkilpeä ovat lahjoituksia, samoin 5 kynttiläkruunua. Yhden kruunuista lahjoitti holvimaalausten kustantaja sen muistoksi, että hän oli sopinut riitansa kaupungin lukkarin Eerik Martinpojan kanssa.
Kirkko on useamman kerran peruskorjattu. Viimeinen korjaustyö tehtiin vuosina 1974-75. Vuodelta 1892 olevien urkujen kunnostamisen yhteydessä nämä 12-äänikertaiset Walckerin urut laajennettiin 22-äänikertaisiksi. Työ valmistui loppiaiseksi 1978.