Iš pradžių Užlieknėje buvo koplyčia, kuriai 1784 m. paskelbti dveji metiniai atlaidai (gegužės 3 d. Šv. Kryžiaus Atradimo ir liepos 22 d. Marijos Magdalenos). 1807 m. kanauninkas Kasparas Bytautas (1769 - 1834-05-04/16) pastatė naują koplyčią, o 1857 m perstatyta; priklausė Viekšnių parapijai. Pokario metais ir dabar bažnyčia nuolatinio kunigo neturi – aptarnaująs Viekšnių klebonas. Bažnyčios šventoriuje pastatytas medinis kryžius Lietuvos krikšto jubiliejui paminėti. Ant kryžiaus yra toks užrašas: 1387 – 1987 Lietuvos krikštui 600 m. Šventoriuje prie vartų stovi senas nedidelis metalinis kryžius įmontuotas į akmenį, statytas 1904 m. atgabentas kartu su bažnyčia iš senosios jos stovėjimo vietos. Panašus kryžius yra likęs ir senoje vietoje. Tebėra ir seni medžiai kadaise supę maldos namus. Užlieknė nuo seno garsėja Marijos Magdalenos atlaidais. Į juos dar tarpukaryje suplaukdavo minios maldininkų. Bažnyčiai priklausė 24 ha ūkis su erdviais trobesiais ir stebuklingu šaltiniu Šventupio upelyje. Stebuklingasis vanduo dvasiškiui duodavo daug pelno.

2007-03-04 bažnyčia apdegė. Sudegė stogas, vidaus perdangų dalis, stipriai apdegė viena siena ir bažnyčios bokštas. Ugnis sunaikino kairįjį šoninį altorių ir šalia jo kabojusį nežinomo autoriaus paveikslą, kuriame buvo vaizduojamas prisikėlęs Kristus.