Pierwszy kościół z całą pewnością istniał w Pszczewie już w XIII w., ponieważ w 1298 r. poznański biskup Andrzej Szymonowicz ustanowił tutaj archidiakonat. Wiadomo też, że kolejną, zbudowaną z muru pruskiego świątynię ufundował w 1446 r. biskup Andrzej Opaliński. Przetrwała ona do pożaru miasta na początku XVI w. Odbudowaną spalili w 1631 r. Szwedzi. Na jej miejscu, z inicjatywy biskupa Andrzeja Szołdrskiego powstał w latach 1632 – 1654 murowany kościół, który stoi do dziś. Przebudowywano go zarówno w XVIII jak i w XIX w.- w efekcie ma dzisiaj formę późnorenesansową z elementami baroku.
Wewnątrz warta uwagi jest XVIII w. ambona i barokowy ołtarz z obrazem św. Marii Magdaleny Pokutnicy - patronki kościoła, poniżej którego umieszczono kopię obrazu Matki Boskiej Rokitniańskiej. Na ścianie przedsionka tablica poświęcona poległym w I wojnie mieszkańcom Pszczewa.
Na terenie przykościelnym zachowało się kilka nagrobków ze starego cmentarza – m.in. zasłużonego pszczewskiego proboszcza Władysława Enna i dwóch powstańców styczniowych – Melchiora oraz Macieja Górnych. W pobliżu głównego wejścia, podczas przekazania i poświęcenia sztandaru dla Związku Leśników Polskich posadzono w 2010 r. cis wyhodowany z nasion pobłogosławionych przez papieża Benedykta XVI.