Pierwotnie podlegał parafii św. Trójcy. Dopiero później, gdy wyodrębniono parafię Podwyższenia św. Krzyża, stał się jej parafialnym cmentarzem. Jego początki sięgają 1894 r. Część terenu pod cmentarz odsprzedał bytomski biznesman Ignatz Hakuba. Początkowo planowano, że będzie połączony z „Mater Dolorosa I” w momencie, gdy zostanie zlikwidowana przebiegająca obok linia kolejowa ROUE, co stało się znacznie później, niż się spodziewano. Cmentarze nigdy nie zostały połączone. Uroczyste jego poświęcenie miało miejsce w dniu 22 listopada 1896 r. Dokonał go ksiądz Reinhold Schirmeisen, ówczesny proboszcz parafii św. Trójcy. Pod koniec XIX w. nekropolia została otoczona murem. Bliskość zakładu opieki medycznej powodowała, że na cmentarzu chowano nie tylko mieszkańców miasta z terenu parafii św. Trójcy, ale również zmarłych pensjonariuszy z Krüppelheim. Brama cmentarna od strony ul. Woźniaka została zaprojektowana przez Theodora Ehla. Wzniesiono ją w 1940 r., ale do dnia dzisiejszego ocalał tylko jej niepozorny i zaniedbany fragment. Początkowo chowano na nim jedynie parafian, jak również zmarłych pacjentów Krüppelheim oraz Zakładu Dobrego Pasterza z ulicy Strzelców Bytomskich, nieistniejącego ośrodka poprawczego dla dziewcząt prowadzonego przez siostry zakonne.
Na tym cmentarzu spoczął Simon Macha, wielki miłośnik historii Bytomia, dzięki któremu w mieście powstało Muzeum Górnośląskie. Jednakże jego grobowiec jest obecnie użytkowany przez inną rodzinę. Jest tu również zaniedbana i mało rzucająca się w oczy mogiła Josefa Hammerlinga, ojca bytomskiego architekta Augusta Hammerlinga, który zaprojektował wygląd nieistniejącego już browaru przy ul. Wrocławskiej. Jest też pochówek architekta Jana Wilka. Spoczęło tu również dwóch ludzi, którzy byli wielkimi miłośnikami historii naszego miasta. Jeden z nich to Maciej Skalski, a drugi to Maciej Zeiskie nazywany „Aniołem”. Kochali Bytom i spoczęli w nim na zawsze. Znajdziemy tu również zbiorową mogiłę górników, którzy zginęli w straszliwym wypadku na kopalni „Dymitrow” (dawna „Karsten-Zentrum”).
Znajdują się tam również groby żołnierzy z okresu I wojny światowej. Niewielkie tabliczki, równo ułożone, niektóre z dodatkiem krzyża w formie niemieckiego odznaczenia wojennego, niektóre z prostym krzyżem (obecnie pozostało tylko kilka z nich). Leży tam blisko 300 żołnierzy, jeńców i nie tylko, zmarłych w bytomskich szpitalach wojennych w okresie I wojny światowej lub krótko po niej. Głównie są to żołnierze niemieccy (w tym Ślązacy), ale również Rosjanie i Serbowie, a zdarzyli się nawet Francuzi i Brytyjczycy (ekshumowani krótko po wojnie). W 1921 r. na ich mogiłach ustawiono krzyże, których część przetrwała do dzisiaj. Leżał tu również kapral Joseph Lennard (ekshumowany w 1923 r.), Brytyjczyk William Davis (ekshumowany w 1924 r.) oraz Francuz ekshumowany w 1926 r. Ekshumowano też innych. Pozostało tam 143 żołnierzy niemieckich, 159 rosyjskich i dwóch serbskich. Płyty niemieckich żołnierzy zostały zwieńczone Krzyżami Żelaznymi, których obecnie zachowało się tylko kilka. Pozostałe zostały rozkradzione. W ostatnim czasie zginęło nawet kilka tablic. W okresie II wojny światowej na tym cmentarzu pochowano siedmiu niemieckich żołnierzy i jednego członka organizacji dywersyjnej „Freikorps Ebbinghaus”.
Na cmentarzu znajduje się również mogiła Poli Maciejowskiej. Paulina, którą nazywaną „Polą” czy nawet „Lolą” urodziła się w dniu 3 lutego 1899 r. w Kowlu na Kresach Wschodnich. W sierpniu 1920 r. wraz z grupą innych studentów Uniwersytetu Warszawskiego wyjechała do Zagłębia Dąbrowskiego. W dniu 17 sierpnia 1920 r. w Będzinie wydano jej dowód tymczasowy na fałszywe nazwisko Szchulz. Brała czynny udział w II powstaniu śląskim (1920). Gdy w dniu 26 września 1920 r. rozłamowcy z PPS-u założyli Komunistyczną Partię Ziem Śląskich, najprawdopodobniej weszła w struktury tej partii. Posługiwała się wtedy pseudonimem „Kałuża”. W 1920 r. została w Miechowicach aresztowana przez policję plebiscytową APo i przewieziona do bytomskiego więzienia. Oficjalna wersja mówi, że w nocy z 10 na 11 listopada 1920 r. popełniła samobójstwo, wieszając się w celi na pasku od sukienki lub na skrawku prześcieradła. Nie ma jednak całkowitej pewności, czy było to samobójstwo, czy morderstwo na zlecenie. Krótko po wojnie została patronką Szkoły Podstawowej nr 12 w Bytomiu (dawnej Georg-Brüning-Schule), a od 1974 r. działającej w tym samym budynku Szkoły Podstawowej nr 5. Bytomski Rynek w czasach PRL-u nosił nazwę Placu Poli Maciejewskiej.
