Fort XIII na Nové ulici byl vystaven v letech 1850-1854 stavební společností bratří Kleinů. Konstrukčně se nelišil od paralelně budovaných fortů XI, XV a XVII. V jádru objektu se nacházel podkovovitý kasárenský objekt (tzv. reduit) s nádvořím a šíjovou kaponiérou. V jeho interiéru bylo 22 kasemat pro ubytování posádky. V běžném provozu zde bylo ubytováno kolem 90-180 mužů, v době cvičení a přípravy pevnosti na obranu 300 až 400. Další důležitou součástí fortu XIII byl mohutný kasematovaný zemní val, který obklopoval reduit. Na valu se nacházela dělostřelecká postavení vzájemně oddělená tzv. traverzami. V době prusko-rakouské války v roce 1866 byla pevnůstka osazena celkem 26 děly. Před valem se nacházel příkop chráněný nejen střílnami umístěnými v jeho vnější zdi (v tzv. kontreskarpě), ale i dvěma bočními dvoukaponiérami. Lidově se jim říkalo „kočičí uši“ a v současnosti jsou na tomto fortu už ubourány. Fort XIII nazývaný Ziegelschlag (kvůli nedaleké cihelně) nebyl nikdy vystaven útoku nepřítele. Pevnůstka sloužila především jako kasárenský objekt, krátkodobě také k internaci vězňů. V roce 1864 zde bylo umístěno 200 Poláků prchajících po tzv. Lednovém povstání z Kongresového království. Po zrušení pevnostního statusu Olomouce (1888) sloužil fort především jako dělostřelecká laboratoř a muniční sklad. Za druhé světové války byla pevnůstka v držení německé armády, která na jejím vnějším valu vybudovala postavení pro protitankový kanón. V květnu 1945 popravili fašisté na tomto objektu 17 vlastenců z Kožušan a z Brodku u Přerova. Tuto tragickou událost připomíná pamětní deska na kontreskarpové zdi. Fort XIII je nemovitou kulturní památkou.