Za fundatora erygowanej przez biskupa poznańskiego Pawła Bnińskiego w 1238 r. służewskiej parafii uważany jest książę Konrad Mazowiecki. Od tego czasu do końca wieku XVIII, kiedy to utworzono diecezję warszawską, parafia podlegała diecezji poznańskiej. W 1245 r. książę Konrad nadał Służew rycerzowi Gotardowi, protoplaście wszystkich rodów herbu „Radwan". Kolejnymi kolatorami kościoła byli: jego potomkowie o nazwisku Służewscy, a od XVIII w. kolejni właściciele dworu służewskiego i dóbr wilanowskich: Czartoryscy, Potoccy i Braniccy.
O pierwszym służewskim kościele wiadomości są znikome. Drugą świątynię – drewnianą, wystawiono w XIII w. Trzecią, w stylu gotyku mazowieckiego, wybudowano w średniowieczu. I tę właśnie z fundacji księcia Augusta Czartoryskiego wyremontowano w 1742 r., a obecny kształt nadał jej Lanci w 1848 r. Dzięki ofiarności proboszcza i potomków (osadzonych w okolicach jeszcze za czasów carycy Katarzyny) Niemców-katolików, świątynia ocalała z pożogi wojennej. Ozdobą – mającego od 1782 r. wezwanie Niepokalanego Poczęcia N.M.P. i Św. Katarzyny z Aleksandrii – frontonu kościoła są głowice romańskie przywiezione przez Lanciego z Włoch i uchodzące za starożytne. Ściany zdobią tablice epitafijne i kommemoratywne z XVIII, XIX i XX wieku oraz od strony południowej zegar słoneczny Wnętrze kościoła. Poza przekutymi z rzeźb średniowiecznych, a więc noszących cechy gotyckie figurami Świętych Wojciecha i Stanisława – barokowe, warsztatu rzeźbiarskiego Jana Plerscha. Najstarszy obraz przedstawia łaskami słynący wizerunek Św. Rocha pochodzenia francuskiego z przełomu wieków XVI i XVII w. Ozdobą kościoła jest wiedeńska Droga Krzyżowa z I połowy XIX w. i organy firmy „Otto Rygier” w szafie, z 1830 r. W centrum ołtarza głównego usytuowany jest krzyż gotycki z przełomu XIV i XV w. Nad nim witraż z wizerunkiem Św. Katarzyny Aleksandryjskiej, patronki parafii.
Dzwonnica służewska w jej obecnym kształcie wzniesiona została (na starym miejscu i prawdopodobnie na starych fundamentach) w 1881 r. Po zniszczeniach wojennych odbudowana dopiero w latach 1991-94. W dzwonnicy obecnie znajduje się 5 dzwonów: XVI-wieczny spiżowy „Ave Maryja”, „Jan Chrzciciel” z 1774 r., wotywny z 1913 r., oraz dwa nowe – „Józef” i „Katarzyna” z 1992 r.
Przy elewacji północnej świątyni, gdzie kiedyś mieścił się cmentarz przykościelny, stoi figura Niepokalanej Maryi Panny, ocalona z Getta Warszawskiego. Od strony wschodniej zaś, ustawione niedawno na niskim cokole, popiersie Ojca Świętego Jana Pawła II. Przed kościołem: Figura N.M.P. z 1902 r. oraz Pomnik Męczenników Terroru Komunistycznego składający się z głazów, które same w sobie są również pomnikami przyrody.
Posesja parafialna zachowała po dziś dzień średniowieczny układ. Na dziedzińcu wysokim znajduje się kościół i dzwonnica; na średnim – plebania; na niskim – pozostałości folwarku i dom katechetyczny. Obok niego stoi drewniany dom z połowy XIX w. w którym obecnie znajduje się zakład pogrzebowy. Jest to jeden z dwóch ocalałych w Warszawie domów drewnianych „typu warszawskiego”.
Plebania wybudowana została w roku 1640. Jest to klasyczny dworek będący nieprzerwanie w ciągu wieków mieszkaniem proboszczów służewskich. Budynek uszkodzony podczas powstania 1794 i wojen napoleońskich, odbudowany został w 1820 r. i gruntownie odnowiony w 1872 r. W. Na plebanii znajduje się obraz M. B. Częstochowskiej, przed którym modlono się gorliwie o zwycięstwo w 1920 r. i przed którym Wojsko Polskie złożyło pierwsze dziękczynienie za zwycięstwo w kościele służewskim już w nocy z 15 na 16 sierpnia 1920 r. W hallu plebanii – ceglana posadzka mazowiecka z XVII w. Natomiast w refektarzu – medaliony postaci historycznych, osób które miały trwałe związki ze służewską parafią: Jana III Sobieskiego, Tadeusza Kościuszki, Juliana Ursyna Niemcewicza i Józefa Piłsudskiego.
Kilkadziesiąt metrów od kościoła w kierunku południowym znajduje się stary cmentarz parafialny. Jego początki giną w pomroce dziejów. Wykopana na nim kiedyś urna z epoki kultury łużyckiej może być śladem informacji o jego starożytności. Na nim to znajduje się grób Krystyny Krahelskiej, której twarz sportretowana została w rzeźbie Syrenki Warszawskiej.