Pierwszą świątynię redzką wzniesiono z drewna w końcu XII wieku z fundacji książąt pomorskich. Świątynia ta znajdowała się w miejscu obecnych sal katechetycznych. Obiekt przetrwał liczne konflikty, w tym potop szwedzki, ale po tej wojnie osada uległa wyludnieniu i kościół zamknięto (parafia została przeniesiona do Rumi). Zamkniętą świątynię strawił pożar po koniec XVII wieku. Ocalały z niej jedynie dwie figury przedstawiające świętych Piotra i Pawła. Drugi kościół został wzniesiony na przełomie XVIII i XIX wieku z muru pruskiego. Przetrwał on do końca XIX wieku i został rozebrany.



Obecna, trzecia świątynia została wzniesiona w stylu neogotyckim w latach 1901-1903 z funduszy państwowych i parafialnych z powodu gwałtownego rozwoju osady[2]. konsekrował ją biskup Jakub Klunder w dniu 26 września 1907 roku i nadał wezwanie św. Katarzyny Aleksandryjskiej. Budowla posiada strzelistą wieżę, w niej znajduje się dzwonnica. W 1956 roku ówczesny redzki proboszcz, ksiądz Arnold Goetze, wielki czciciel Maryi, poprosił Kazimierza Kowalskiego, biskupa chełmińskiego o zmianę wezwania świątyni i parafii na pamiątkę ogłoszenia dogmatu o Wniebowzięciu Matki Boskiej. Biskup zgodził się i od 1957 roku kościół i parafia noszą wezwania: Wniebowzięcia Najświętszej Maryi Panny i św. Katarzyny Aleksandryjskiej.



Tablice pamiątkowe i otoczenie

Na zewnętrznej elewacji umieszczone są trzy tablice pamiątkowe. Dwie z nich upamiętniają mieszkańców Redy poległych na frontach II wojny światowej, a także zamordowanych przez niemieckich faszystów. Trzecia zawiera cytat z kardynała Stefana Wyszyńskiego: Sztuką jest umierać dla Ojczyzny, ale największą sztuką jest dobrze żyć dla niej.



Przy kościele znajduje się kamienna grota maryjna.