Sent på kvelden den 5 mai 1909 ble den gamle korskirken på Leines totalskadd av brann. Den hadde da vært menighetens samlingssted i over 100 år. Det oppsto først brann i et nabohus som lå like i nærheten av kirken. Folk klarte å redde ut en del av kirkens innbo, altersølvet, døpefonten og en del av kirkebenkene ble reddet. Som en midlertidig ordning ble skolelokalet på Leines godkjent og innvidd til interimskirke. Selv om brannen kom som et sjokk på befolkningen gikk det ikke lang tid før arbeidet med reising av en ny kirke ble tatt opp, alle var klar over at gjenreisingen ville bli en stor påkjenning for den økonomiske svake kommunen, men dette var ikke det vesentligste problem som meldte seg. Det viste seg snart at det rådde en ganske sterk meningsforskjell om hvor ny kirken skulle plasseres. Tidligere kirker har stått på leines, altså i en ytterkant av kommunen, og nå var det mange som mente at en plassering nærmere midtpunktet av soknet ville være å foretrekke. Sommeren 1909 behandlet Leiranger herredsstyre spørsmålet om byggested for kirken og vedtok da å trekke bygdefolket inn ved en folkeavstemming om kirketomt i Leinesfjord eller på Leines. Avstemmingsresultatet ble lagt fram for herredsstyre i november 1909 der flertallet ble for Leines. Avgjørelsen ble anket av mindretallet og saken gikk til Kirke- og undervisningsdepartementet, som innhentet uttalelser fra de meningsberettigede instanser, og til slutt havnet saken på regjeringens bord. I november 1910 kom telegram fra kirkedepartementet til ordføreren i Leiranger med melding om vedtak at Leiranger kirke skulle gjenoppføres på Leines. Biskop Dietrichson i Tromsø uttalte følgende: Etterslekten vil beklage det dersom kirken ikke blir plassert på Myklebostad (Leinesfjord)
Det ble arkitekt Nils Ryjord i Trondheim som ble engasjert i å arbeide ut byggetegninger og kostnadsoverslag for en kirke med 500 sitteklasser. Byggmester O. M. Olsen fra Ørnes fikk oppdraget med oppføringen av den nye kirken og kontrakten ble skrevet 21 april 1911 og ferdigstillelse til utgangen av oktober 1911. i slutten av november 1911 sto bygget ferdig og formelig lyste opp i omgivelsene med sin friske lysgule farge.
Innvielsen av den nye Leiranger kirke skjedde 6 desember 1911 av biskop Dietrichson som betegnet kirken som stiftets vakreste kirke, og meget praktisk innredet.
Søndag 5 juni 2011 feiret kirken 100 års jubileum med biskop Tor B. Jørgensen og festmiddagen på Leines skole etter jubileumsgudstjenesten ble arrangert av Leiranger menighetsråd.