Pärast Tallinna vallutamist 1710. aastal ehitasid venelased mõne aasta pärast Kalaranda puitmuldfordi. Fordi nimena on esinenud Eestimaa patarei ja Läänepatarei, sellest pärineb hiljem ka Väike- ja Suur-Patarei tänava nimi.
Aastail 1819–1820 koostati Tallinna jaoks uus kaitsekava, mis nägi ette vana puitmuldfordi asemel uue kivifordi rajamise. Selle kava kinnitas mais 1820 keiser Aleksander I.
Vana fort lammutati 1829. aastal, uus kivifort rajati põhiosas aastatel 1830–1837. Fordi põhiosa ruumid toimisid kaitsekasarmuna, seetõttu on forti ametlikus vene keeles nimetatud ka kaitsekasarmuks (Оборонительная казарма) või kaitsekasarmuteks (Оборонительные казармы).
Alates 1863. aastast on forti kasutatud hariliku kasarmuna. Seetõttu juurdus tasapisi rahvasuus nimi "brigaadikasarmud" või "patareikasarmud" sealpaiknevate jala- ja suurtükiväeuksuste järgi.
Aastatel 1919–2005 tegutses fordis vangla peamiselt nimega Keskvangla, ametlikult on olnud kasutusel eri aegadel muid nimetusi. Seetõttu tuntakse alates 1920. aastate lõpust kompleksi üldiselt rahvapärase nimega Patarei (vangla). Tänapäeval on eriti rahvapäraselt kasutusel mitmed kombineeritud (üldiselt vigased) nimed (nt Patarei merekindlus vms).
Põhjalikumalt Wikipedias.