Stenkyrkan är troligen uppförd vid slutet av 1300-talet eller under 1400-talets första hälft. Sidensjö omnämns första gången i ett brev från ärkebiskop Henricus Karoli. Brevet är daterat den 17 juli 1386.'
Då var församlingen annex till Nätra kyrka. Enligt sägnen påbörjades kyrkobygget på 1300-talet, men avbröts på grund av digerdöden. Digerdöden ödelade många byar. Det kom även att påverka pastoratets sammansättning. Flera socknar fick slås samman till ett pastorat med en präst.
Kyrkobygget fullföljdes först, när bygden återhämtat sig på 1400-talet. Då utrustades byggnaden med vapenhus och kyrkorummet försågs med två stjärnvalv av tegel. Flera senmedeltida träskulpturer och fragment av kalkmålningar från 1600-talet har bevarats.
En av träskulpturerna föreställer sannolikt kyrkans skyddspatron Sankt Laurentius. Han är klädd i en vit fotsida mässkjorta,alba. Över den bär han en dalmatika, mässhake med ärmar. Mässhaken är randad, kanske är ränderna märken efter det halster, på vilket helgonet led martyrdöden.
Triumfkrucifixet från 1500-talet framhåller den lidande Kristus. Bildframställningarna under 1300-talet , digerdödens århundrade, poängterar Kristi fysiska smärta. I Norrlands provinsiella arbeten kom Jesu lidande att betonas ända fram till reformationen.
Predikstolen, baldakinen över predikstolen, den nedre orgelläktaren och korskranket är tillverkade mellan åren 1727-1731 av den kände bildhuggaren och snickaren Magnus (Måns) Gran bosatt i Härnösand.