Kroniki zanotowały ośrodek misyjny benedyktynów na krawędzi skarpy. Nieopodal przebiegało stare koryto Wisły. Rokiem zanotowanym przez kronikarzy był 1065. Niewiele wiadomo o tamtej misji, zapewne mnisi korzystali z drewnianej kaplicy. Kolejną datą, która pojawia się w kontekście kościoła, jest ufundowanie w 1238 roku parafii przez księcia Konrada Mazowieckiego. Patronką została św. Katarzyna. Konrad, znany nam ze sprowadzenia Krzyżaków, miał w utworzeniu parafii swój polityczny plan. Co ciekawe, był on tożsamy z sprowadzeniem samych rycerzy Zakonu Najświętszej Maryi Panny. Był to bowiem projekt umocnienia granic przed najazdami Litwinów i pruskich Jaćwingów.
Utworzony kościół miał być murowany i wraz ze skarpą tworzyć kompleks obronny. Pod stromą skarpą i zapewne jedną zaledwie drogą pod górę biegła fosa, czego pozostałości przetrwały w nazwie ulicy Fosa. Kościół otoczony murem być może posiadał również wał u podnóża skarpy lub inne fortyfikacje. Fragmenty dawnej świątyni są obecne w kościele św. Katarzyny. Tego typu świątynie powstawały licznie na terenach rodzącego się państwa krzyżackiego i pełniły funkcje refugialno-obronne. Z pewnością już wówczas powstały w tym miejscu pierwsze pochówki - taka praktyka była normą w ówczesnej Europie. Co ciekawe na miejscu nawet znaleziono urny ciałopalne z czasów kultury łużyckiej. Można więc śmiało twierdzić, że tradycje pochówku w tym miejscu sięgają czasów przedstarożytnych!
Kiedy pierwotny cmentarz?
Niewiele wiemy o pierwotnej nekropolii. Zachowały się bowiem tylko trzy groby kominowe. Stara jest również stojąca przy wejściu stoi figura Najświętszej Maryi Panny, która była ukrywana podczas zaborów na plebanii. Niestety, cmentarz na Służewie został zniszczony w czasie Powstania Listopadowego. Odnowienie i rekonsekracja miała miejsce w 1839 roku. W roku 1850 powiększono obszar cmentarza i obwiedziono go murem. Ponownie dokonano zwiększenia obrysu nekropolii w 1876. Na miejscu swoje groby miało wiele znanych rodzin warszawskich.
Ważną datą jest bez wątpienia 8 października 1989 roku. Wówczas prymas Józef Glemp na terenie cmentarza złożył ziemię pobraną z miejsc egzekucji i pochówków ofiar komunistycznego terroru. Wśród nich była ziemia z terenów obu służewskich cmentarzy, skarpy warszawskiej, służewskiego klasztoru dominikanów, toru wyścigowego na Służewcu, Powązek i okolic ulicy 11 listopada. Złożono ją w miedzianej urnie wykonanej przez artystę Andrzeja Renesa.
To tu pochowano warszawską Syrenkę
Zdecydowanie najbardziej znaną postacią pochowaną na cmentarzu na Służewie jest Krystyna Krahelska. Ta malarka i poetka znana jest z udzielenia wizerunku warszawskiemu symbolowi. W latach 1936-1937 pozowała prof. Ludwice Nitschowej, autorce pomnika warszawskiej Syreny.
Wiersze i piosenki Krahelska pisała od 1928 roku. Najbardziej znaną swoją piosenkę "Hej, chłopcy, bagnet na broń!" napisała w styczniu 1943 r. dla żołnierzy "Baszty", a odśpiewała im na tajnym koncercie w lutym 1943 w mieszkaniu podporucznika czasu wojny "Michała" Ludwika Bergera przy ul. Czarnieckiego 39/41. Stała się ona najpopularniejszą piosenką żołnierską Polski Walczącej i Powstania Warszawskiego. Artystka zginęła jako sanitariuszka Powstania Warszawskiego 2 sierpnia 1944.
Na cmentarzu znajdziemy również wiele grobowców zasłużonych warszawiaków. Pochowani sa tu m. in.: Andrzej Bednarek (1949-2003) – filantrop, entomolog, profesor SGGW; Jan Blinowski (1939-2002) – fizyk, profesor UW; Zygmunt Bogacz (1932-1981) – docent SGGW i Władysław Chrapusta (1896-1982) – dziennikarz, uczestnik wojny polsko-bolszewickiej.
