Budova Okresního soudu v Břeclavi, jejíž součástí byla okresní věznice, byla postavena na sklonku 19. století v novorenesančním duchu jako celá řada dalších veřejných budov v Břeclavi té doby.
Byla stavěna pro potřeby okresního soudu , který zde vznikl v roce 1850 po reformě státní zprávy způsobené revolučními událostmi roku 1848. Tehdy byla zrušena soudní pravomoc patrimoniálních úřadů (správ příslušného velkostatku, který vykonával veškeré správní a soudní pravomoci k poddaným panstvím) a se zánikem poddanství vznikly nové správní a soudní orgány. Pod pravomoc okresního břeclavského soudu spadaly obce Nová a Stará Břeclav, Židovská obec Břeclav a Podivín, město Podivín a vsi Lanžhot, Kostice, Tvrdonice, Mikulčice, Týnec, Moravský Žižkov, Ladná, Velké Bílovice a Hrušky.
Okresní věznice byla určena pro krátkodobé tresty odsouzených ze spádové oblasti břeclavského soudu. Ke krátkodobým trestům nastupovali odsouzení s vlastním jídlem, např. chlebem a špekem a pitím – mnohdy i s demižónem vína.
Věznice ukončila svoji činnost v roce 1953. Od roku 1959 byla budova předána Okresnímu národnímu výboru. Později zde byl až do roku 1989 vojenský útvar pohraniční stráže.
V roce 1990 byla budova převedena Okresnímu soudu, který jednu část budovy nechal zrekonstruovat pro svoji potřebu a druhá část byla určena pro stavbu věznice.S výstavbou nové věznice bylo započato na jaře roku 1993, stavba byla ukončena na jaře roku 1995. Od té doby byl také zahájen provoz vazební věznice jako objektu Vazební věznice Brno.
Dnem 1. ledna 1997 byla rozhodnutím Ministra spravedlnosti ČR zřízena samostatná Vazební věznice Břeclav, která se k 1. 1. 2006 stala v rámci reprofilace věznicí pro odsouzené muže zařazené do výkonu trestu odnětí svobody s dohledem a ve věznici s ostrahou.
K 1. listopadu 2012 se Věznice Břeclav rozrostla o objekt Poštorná, který byl slavnostně otevřen 23. listopadu 2015.