Puinen kirkko valmistui vuonna 1811. Rakentaja on Matts Åkergren. Muodoltaan kirkko on niin sanottu oktagonkirkko eli kahdeksankulmainen pitkittäiskirkko. Teologinen selitys kirkon muodolle on, että kuusi kirkon kahdeksasta sivusta kuvaa Jumalan luomistyön kuutta työpäivää ja seitsemäs lepopäivää. Kahdeksas sivu kuvastaa iankaikkisuutta.

Istumapaikkoja kirkossa on noin 300.

Heinolan kirkon urut

Kirkon urut on valmistanut Kangasalan urkutehdas vuonna 1972 (opus 884 28/III m). Urut ovat mekaaniset ja niissä on 28 pillisarjaa eli äänikertaa ja kolme sormiota. Soivia pillejä on 1758. Äänikertasuunnittelu Asko Rautioaho, julkisivu Pentti Pelto, äänitys Pekka Vuori.

I OW   Gedackt 8', Salicional 8', Principal 4', Blockflöte 4', Oktave 2', Sifflöte 1 1/3', Scharf 3x, Dulzian 8', Tremolo.
Il HW    Principal 8', Rohrflöte 8', Oktave 4', Oktave 2', Mixtur 3-4x, Trompete 8', O-H, B-H.
III BW  Holzgedackt 8', Gedackt 4', Nasat 2 2/3', Waldflöte 2', Terz 1 3/5', Zimbel 2x, Regal 8', Tremolo.
P          Subbass 16', Principal 8', Gedackt 8', Oktave 4', Mixtur 3x, Fagott 16', Oboe 4', H-P, O-P, B-P.