Pokud se dá věřit ústnímu podání a tradici, mělo by být Předmostí starší něž samotný Přerov, když na „Svatovojtěšské skále“ zanechal své vytlačení stopy sám sv. Vojtěch … Jméno „Předmostí“ dostala obec pravděpodobně až v době, kdy byl v Přerově postaven stálý most přes řeku Bečvu, někdy ve 12. nebo ve 13. století.
Zdejší kostel určitě stál už v roce 1362, protože zápis v zemských deskách z tohoto roku uvádí předmostského faráře Macúrka. V roce 1769 byl při kopání základů pro novou zákristii nalezen náhrobník z roku 1526, jenž nese erb a dodnes čitelný nápis: Léta 1526 v úterý po sv. Bartoloměji umřela jest urozená paní Kateřina, manželka pana Kunše z Vrchlabí a na Čekyni, a tuto pochována. (Leta M-CCCCC-XXVI w vtery po Swatem Bartholomiegi vmrzela g(es)t Vrozena panij Katerzina Manželka Pana Kunsse z Wrchlabie a Na cžekin, a tuto pochowana.) Je zazděn na vnější straně presbytáře. K předmostí byly totiž přifařeny také vsi Čekyně, Popovice, Lýsky, Vinary a Dluhonice, do roku 1784 také Buk a Prosenice.
Samostatná farnost zanikla v době třicetileté války. Předmostí bylo připojeno prokazatelně od roku 1629 jako komenda k Přerovu. Teprve 4. května 1661 bylo zdejší obročí opět osamostatněno a obsazeno Janem Aloisem Korneliem, který si v popisu farnosti v tzv. Děkanské matrice v roce 1672 trpce stěžoval na zubožení kostela i beneficia.
Farářem Korneliem začala souvislá řada předmostkých farářů, která skončila P. Norbertem Jiřím Viačkou, od té doby je Předmostí opět spravováno z Přerova. Patronem kostela se v josefínské době stal Religionsfond, později jim byla Náboženská matice, v padesátých letech 20. století byly patronáty zrušeny. Původní obec prakticky smazala z tváře země výstavba sídliště v letech 1975-1980.
Kostel býval obklopen obezděným hřbitovem, definitivně zrušeným v roce 1943. Podle zmíněné Děkanské matriky byl kostel kratší – sahal zhruba po dnešní podpěry kůru. Až do ruku 1769 nebyl klenutý, měl plochý dřevěný strop a v místě dnešní zákristie vysokou starou věž, už sešlou.
Roku 1769 začal tehdejší farář František Schaurek s přestavbou kostela – věž byla zcela zbourána, kostel prodloužen a zaklenut, nad hlavním vchodem byla postavena nová zvonice vysoká 13,3 m. Nová zákristie s oratoří byla postavena u jižní stěny kostela. Letopočet dokončení přestavby MDCCLXXII (1772) je vytesán v překladu hlavního vchodu. Mimo vlastní stavbu se z této doby uvnitř kostela nezachovalo nic. Dne 2. září 1831 byl kostel zasažen požárem, šířícím se z hořícího Přerova, a spolu s částí vesnice, školou a farní stodolou padl v oběť plamenům. Pro bohoslužby byl jenom nouzově zajištěn.
Důkladné opravy kostela, věže a hřbitova začal až roku 1845 farář Josef Homm. Skončily v letech 1852 a 1853, proti ohni dal pokrýt střechu kostela břidlicí. Bohužel Pamětní kniho o tom uvádí jen to, že ,,hlavní oltář se dvěma bočními oltáři spolu s figurami a také oltářními obrazy zcela nové; dále kazatelna, která byla předtím na druhé straně jako chlebová ošatka u země, byla nově pořízena, upevněna na protější stěně a prolomen u ní příchod. Proti kazatelně byla zavěšena úplně nová křtitelnice a vše bohatě ozdobeno. Také byly nově udělány některé lavice.“
Roku 1863 k miléniu příchodu věrozvěstů sv. Cyrila a Metoděje na Moravu byly zásluhou administrátora Oldřicha Brázdila, zaníceného vlastence, postaveny jejich sochy po stranách hlavního vchodu do kostela.
Barokní střecha věže byla v roce 1880 přestavěna do dnešního tvaru, kostel vylíčen vně i uvnitř a ještě bylo ,,vydlážděno před kostelem a chodník až k sakristii, dány železné branky na hřbitov, pak zídka okolo kostela opravena, dány boční dvéře dubové ku nové přistavené předsíni zákristie … Všechny tyto věci byly do 7. listopadu 1886 hotové a den tento byl dnem radostným pro Předmostí, neboť se konalo všech těch zjednaných věcí posvěcení za hřímání děl. … Mnoho vykonáno s přispěním Božím a provždy památka tu zůstane velebnému pánu Josefu Štefkovi, který všechny tyto věci obstaral a provedl.“
V roce 1914 byla firmou Křižík z Prahy provedena elektroinstalace v kostele i na faře.
Od roku 1906, kdy byla zcela vyměněna vazba i krytina střechy, čekal kostel na důkladnou opravu až do roku 1950 za působení administrátora ThDr. Aloise Otzipky. Dne 18. března 1954 připsal farář do Pořadu služeb Božích stručné zhodnocení svého díla: ,,Opravil jsem kostel 565.000 Kčs, koupil varhany 696.000 Kčs, koupil zvon, korouhve, koberce, lustr; všechny své úspory i za koncentrační tábor, kde jsem 5 let strávil za Hitlera, jsem zde obětoval. Omnia ad majorem Dei gloriam. Otzipka Alois, farář.“
26. června 1962 rozhodla školská a kulturní komise ONV v Přerově o zápisu kostela sv. Maří Magdaleny do Seznamu státních nemovitých kulturních památek v kraji Severomoravském.
Generální opravou prošel kostel v letech 1970-1972, kdy administrátor Norbert Jiří Viačka zorganizoval výměnu břidlicové krytiny střechy za hliníkový plech, opravu vnitřních i vnějších omítek, restaurování maleb a obrazů atd., všechno za pomocí farníků a z jejich peněžních darů. Opravy skončily právě 200 let po velké přestavbě.
V roce 2008 byla opravena fasáda věže kostela a v roce 2009 pak oklepána a provedena kompletně celá fasáda kostela. Od tohoto času byla barva zelená nahrazena barvou starorůžovou.
Prosím o strpení, stránka v úpravě.