Na początku XIX wieku w miejscu parku znajdował się największy w ówczesnej wsi Żelechowa cmentarz komunalny (niem. Bredofer Friedhof). Cmentarz po rozbudowie w 1904 r. zajmował tereny ok 10 ha i służył mieszkańcom jeszcze w okresie powojennym. Pochowane tu zostało m. in. znane szczecińskie małżeństwo mecenasów sztuki - zmarły w 1820 r. Carl Gotthilf i Carolina Augusta, zmarła 1854 r. Kaplica cmentarna, zachowana do dziś jako kościół Matki Boskiej Ostrobramskiej, stanęła tu w 1911 r. Cmentarz został zniszczony w czasie bombardowań w 1944 r. Po wojnie tablice nagrobne zostały użyte m.in. do utwardzenia brzegów położonego niedaleko Stawu Brodowskiego (przy ul. Stawowej), będącego pozostałością po zatopionej kopalni gliny. W latach 60. XX w. istniały plany zasypania stawu, których ostatecznie nie zrealizowano.
W latach 70. XX w. teren uprzątnięto i nadano mu nazwę Parku Brodowskiego, która obowiązuje do dziś. Od lat 90. park pełni funkcje rekreacyjne, urządzono tu m. in. plac zabaw, wzdłuż alejek ustawiono ławki. Ścieżki zachowały swój dawny cmentarny układ. W parku rosną przede wszystkim stare drzewa liściaste takie jak buk zwyczajny, brzoza brodawkowata, kasztanowiec oraz jesion zwyczajny.