Zvoleňský kostel představuje jeden z nejpomalu rodících se projektů své doby. Starší farní kostel, který předcházel současné stavbě, byl zcela zničen požárem v roce 1854. Toto neštěstí se stalo výchozím bodem pro zcela novou výstavbu. Na podnět olomouckého arcibiskupa Bedřicha z Fürstenberka byly v roce 1858 schváleny plány na nový chrám. Základní kámen byl položen v roce 1860, a po dvou letech, v roce 1864, byly do věže zavěšeny zvony, které měly neznámou dobu sloužit věřícím. Stavba pak byla slavnostně vysvěcena kardinálem Fürstenberkem 2. července 1876, kdy byla také dedikována Neposkvrněnému početí Panny Marie.

Kořeny zdejší sakrální tradice však sahají hluboko do minulosti. První písemná zmínka o obci Zvoli se datuje do roku 1273, a pouhých dva roky později byl zaznamenán tamější filiální kostel sv. Jiljí. Tento starší chrám zažil bouřlivé dějiny – během husitských válek byl zničen a musel být znovupostaven až v roce 1444. Doba renesanční přinesla nové úpravy: za Petra ze Žerotína byl kostel kolem roku 1500 zvětšován, a v roce 1611 prošel další, už větší přestavbou.

Architektonicky se jedná o jednolodní stavbu se mírně odstupněným presbytářem s polygonálním zakončením. Fasáda kostela je dvoubarevná, členěná lizénami s ozdobnými obloučkovými římsami. Dominantou stavby je štíhlá hranolová věž zakončená vysokým jehlanovitým vrhem s makovicí a dvojitým křížem. Boční zdi jsou prolomeny novorománskými okny. Průčelí určuje portál s dvěma sloupy z pískovce, který vyzdobil renomovaný vídeňský sochař Josef Heinrich. Nad ním jsou vyznačeny dva erby – olomouckého arcibiskupství a rodiny Fürstenberků. Stejný umělec vytvořil sochu Panny Marie umístěnou v níši nad oknem.

Interiér kostela je stejně bohatý jako jeho vnější podoba. Vnitřní prostor tvoří široká loď s valcovou klenbou a presbytář s krížovou klenbou. Strop zdobí medailony s biblickými náměty a kulatými portréty světců. Zvláštní pozornost si zaslouží tři barokní oltáře, které pocházejí ze čtyřicátých let 18. století a byly původně součástí olomouckého dómu sv. Václava. Jejich sochařskou výzdobu zajistili významní regionální umělci Jan Kammereit a Ondřej Zahner. Obraz Neposkvrněného početí Panny Marie na hlavním oltáři pochází od vídeňského malíře Dobiášovského. Varhanami opatřil chrám bratr Karel Küttler z Opavy. Kazatelna a křtitelnice jsou zhotoveny z červeně zbarvovaného ostřihomského mramoru z brněnské dílny Josefa Arnolda.

Okolí kostela vytváří harmonický celek. Kostel je situován u silnice ze Zábřeha na Mohelnici, před jeho průčelím se rozprostírá malé dlážděné prostranství. Na západní straně stojí hřbitov obklopený ohradní zdí. Po pravé straně kostela lze nalézt barokní sochu sv. Jana Nepomuckého z roku 1717, kterou chrání status kulturní památky od roku 2003. Levněji je situováno kamenné sousoší Kalvárie z roku 1885. V zahradě mezi kostelem a farou stojí pískovcový sloup se sochou Panny Marie Immaculaty datovaný do roku 1684.