Tvirtovės statyba vyko nuo 1833 m. iki 1842 m. pagal inžinieriaus generolo Karlo Opermano (Карл Иванович Опперман) projektą. 1864–1888 m. tvirtovė buvo modernizuota, be to, įrengtas ją juosiantis atskirų fortų 32 km skersmens žiedas. 1913 m. pradėtas statyti antrasis fortų žiedas, kurio skersmuo turėjo būti 45 km, bet iki I pasaulinio karo pradžios nebuvo pastatytas. 1915 m. rusų kariuomenė atsitraukdama be mūšio paliko tvirtovę, susprogdindama jos atskirus objektus.

1918 m. kovo 3 d. tvirtovėje po Sovietų Rusijos ir Vokietijos derybų pasirašyta Brest-Litovsko taika. 1919–1939 m. tvirtovė priklausė Lenkijai (miestas vadintas Brestu prie Bugo, lenk. Brześć nad Bugiem). SSRS ir Vokietijai okupavus Lenkiją, 1939 m. rugsėjo mėn. mieste įvyko bendras SSRS ir Vokietijos kariuomenių pergalės paradas, pažymėjęs miesto ir tvirtovės užėmimą. 1941–1944 m. Brestas vėl buvo okupuotas vokiečių; tvirtovės apsiaustis 1941 m. truko mažiau kaip mėnesį.

1965 m. Bresto tvirtovė oficialiai gavo vieną garbingiausių tuometinėje SSRS tvirtovės-didvyrės vardą, įvertinusį tvirtovės gynėjų didvyrišką kovą nelygioje kovoje su okupacine vokiečių kariuomene. Šis istorijos epizodas įamžintas daugelyje tarybinių filmų, knygų, mene, atvaizduotas ant Baltarusijos valiutos banknotų. Įrengtas vienas didžiausių II Pasaulinio karo aukų atminimo memorialų, kuris gausiai lankomas turistų.