Cmentarz został utworzony w 1921 r. na północnym skraju fortu kobryńskiego. Powstał on z przeniesienia cmentarza wojennego z czasów I wojny światowej, zlokalizowanego przy kościele parafialnym, od ul. 3-go Maja. Ulokowano go w odległości 100 m na wschód od starego garnizonowego cmentarza rosyjskiego. Zajmował wówczas obszar 2 ha. Na tym cmentarzu grzebano żołnierzy i oficerów pracujących w Twierdzy Brzeskiej. Po wybuchu II wojny światowej pochowano tu kilkunastu żołnierzy polskich, którzy we wrześniu 1939 r. bronili twierdzy przed Sowietami. Znanych jest 17 nazwisk tych żołnierzy, jednak z powodu sprzeciwu władz białoruskich nie zostali oni imiennie upamiętnieni. Na podstawie ksiąg parafialnych Brześcia ustalono, że na tym cmentarzu spoczywa też 5 osób rozstrzelanych i zmarłych 22 i 23 czerwca 1941 r. na terenie kolonii Rzeczyca. Są to: Zbigniew Sługowiecki (zabity pociskiem), Stanisław Feodorko (rozstrzelany), Józef Czyż (rozstrzelany), Józef Mieczysław Czyż (rozstrzelany) i Edward Sługowiecki (zmarł na udar serca). Cmentarz zajmuje lewą (mniejszą) część nekropolii przy ul. Gierojów. Prowadzi do niego osobne wejście, przy którym umieszczono tablicę informacyjną z napisem: "Polski cmentarz garnizonowy". Zrekonstruowany cmentarz ma ponad 550 bezimiennych krzyży, 3 imienne, 11 krzyży prawosławnych i 86 starych zrekonstruowanych grobów, a także dwie zbiorowe mogiły żołnierzy WP, którzy bronili w 1939 r. Brześcia przed Armią Czerwoną - łącznie jest 656 mogił. W 1944 r. po przejęciu miasta przez władze radzieckie nakazano wytyczyć miejsce na cmentarz bohaterów Związku Radzieckiego oraz oficerów kadry wyższej i działaczy partyjnych. Nowy cmentarz zlokalizowano pomiędzy obydwoma cmentarzami garnizonowymi (polskim i rosyjskim). Gdy nowy cmentarz zaczął się rozrastać, "pochłonął" cmentarze garnizonowe. Rosyjski cmentarz garnizonowy z XIX wieku przestał istnieć, ocalało z niego tylko kilka nagrobków. Taki sam los spotkał polski cmentarz garnizonowy, który zamknięto ostatecznie w 1985 r. W 1995 r. wycięto na nim krzewy i wtedy okazało się, że ocalały cztery nagrobki indywidualne żołnierzy z garnizonu brzeskiego, zmarłych w 20-leciu międzywojennym (Tadeusz Liwski, Edmund Jaworski, Telesfor Kaniasty i Stefan Zasadziński) oraz nagrobek ku czci poległych 1.11.1935 r. żołnierzy z 35 pp. Podczas renowacji cmentarza przeprowadzonej w 2000 r. z funduszy Rady Ochrony Pamięci Walk i Męczeństwa wytyczono dwie zbiorowe mogiły żołnierzy poległych we IX 1939 r. Wszystkie polskie groby na cmentarzu otrzymały jednakowe krzyże, tylko trzy z nich są imienne. 10.11.2000 r. odsłonięto na uporządkowanym cmentarzu upamiętnienie główne. Teren kwatery polskiej został podzielony dwiema krzyżującymi się alejkami. W polach grobowych znajdują się różnorodne nagrobki, usytuowane bez żadnego planu, są wśród nich groby cywilne i wojskowe, jest też kilka grobów rosyjskich. Krzyże wojskowe bezimienne, stawiane współcześnie, również nie zachowują symetrii. W części centralnej znajduje się krzyż stojący na ostrych głazach, obok niego umieszczono współczesną tablicę inskrypcyjną z napisem: "Pamięci żołnierzy Wojska Polskiego / garnizonu brzeskiego z lat 1921-1939 / obrońcom Twierdzy Brzeskiej / poległych we wrześniu 1939 r. / Spoczywających na tym cmentarzu / Rodacy 2000. ROPWiM". Z tyłu za upamiętnieniem głównym wtopiono w chodnik resztki starych krzyży z inskrypcjami. 4.10.2001 r. prof. Andrzej Kola dokonał ekshumacji zwłoki oficera WP poległego we wrześniu 1939 r. i pochowanego na prywatnej posesji przy ul. Wierzbowej. Szczątki te pochowano na cmentarzu garnizonowym - grób usytuowano przy skrzyżowaniu alejek cmentarnych. Na grobie umieszczono inskrypcję: "Nieznany oficer Wojska Polskiego, poległ we wrześniu 1939 r. W latach 1939-2001 spoczywał w Brześciu przy ul. Wierzbowej." W 2009 r. Konsulat Generalny RP w Brześciu zidentyfikował i odnowił grób st. sierż. Wacława Boruckiego z 6 batalionu saperów, stacjonującego w okresie międzywojennym w garnizonie wojskowym Twierdzy Brzeskiej. Borucki zmarł w 1935 r. Dzięki zachowanej fotografii grobu z 1935 r. udało się zidentyfikować bezimienny do niedawna nagrobek. Grób nosił ślady zniszczenia - brakowało tablicy imiennej, krzyża wieńczącego pomnik, symbole jednostki wojskowej były słabo czytelne, beton nagrobka był porośnięty mchem. Po oczyszczeniu i zakonserwowaniu nagrobka umieszczono na nim tablicę inskrypcyjną z napisem polskim (uzyskano na to zgodę miejscowych władz).