Budowę kościoła w Brodach rozpoczęto w 1584 roku – ufundował ją pw. swojego patrona Stanisław Żółkiewski – jednak istniejąca do dziś świątynia powstała z fundacji Koniecpolskich. W latach 1620 – 1629 liczne najazdy tatarskie spowodowały zniszczenia kościoła, który został odbudowany w 1629 roku. W 1696 roku świątynię konsekrowano pw. Podwyższenia Krzyża Świętego.
W 1859 roku kościół uległ ponownie zniszczeniu spowodowanemu pożarem. Mimo zniszczenia świątynia zachowała swoją pierwotną formę – jednonawową, w stylu renesansowym. Jest to budowla na planie prostokąta, z pięciobocznym prezbiterium, dwiema symetrycznie rozmieszczonymi kaplicami bocznymi i obszerną, piętrową zakrystią.
Po obu stronach nawy (patrząc w kierunku głównego ołtarza) znajdują się kaplice boczne – kaplica z prawej strony poświęcona była Matce Boskiej Częstochowskiej, po lewej – św. Antoniemu. Z kaplicą św. Antoniego łączyła się kaplica św. Teresy. Nad zakrystią, znajdował się skarbiec. W ołtarzu głównym zawieszony był obraz Chrystusa na krzyżu. Ołtarz i ambona wykonane były z drewna „snycerską robotą”. Nad głównym wejściem znajdowały się organy, obejmowały one „kompletne oktawy z 44 mutacjami i 54 klawiszami bez pedałów”. Przed balaskami z lewej i prawej strony znajdowały się ołtarze boczne – po lewej Matki Boskiej Dobrej Rady, po prawej Pana Jezusa. Posadzka wyłożona była czarnymi i białymi płytkami.
Pod podłogą nawy i kaplic znajdują się krypty grobowe. We wnętrzu nie ocalały żadne elementy dawnego wyposażenia. Neobarokowe malowidła z 1859r. zostały zamalowane w 2004r. Do 1945 r. w kościele znajdował się obraz Matki Bożej – wykonana w 1900r. kopia Madonny Częstochowskiej.

Został zabrany przez wyjeżdżających na zachód Polaków i znajduje się obecnie w kościele pw. Matki Bożej Bolesnej w Opolu.
Po lewej stronie od głównego wejścia znajdowała się dzwonnica. Nad dachem, zwieńczonym niegdyś niewielką wieżyczką, wznoszą się dziś nowo wybudowane cerkiewne kopuły na ośmiobocznych bębnach. Fasadę wieńczy trójkątny szczyt.

W 1946 roku za czasów sowieckich kościół zamieniono na salę sportową, a sygnaturkę rozebrano. Po upadku komunizmu kościół na trzy lata (1990 – 1993) odzyskali rzymscy katolicy, ale już w 1993 roku został przekazany grekokatolikom i do dziś pozostaje w ich rękach, służąc jako cerkiew.

W 1993 roku rozpoczęto budowę nowego kościoła.