Tvrđavu Fetislam čine dve fortifikacione celine iz različitih epoha: Mali i Veliki grad. Najpre je 1524. po zapovesti sultana Sulejmana Veličanstvenog podignut Mali grad, kada komandat turske vojske Bali-beg, u cilju ratovanja sa Ugarskom, podiže znatno jače utvrđenje i daje mu ime Fethi Islam (Fetislam). U vreme austrijsko-osmanskih ratova (između 1717. i 1737. godine) oko postojeće tvrđave podignut je Veliki Grad sa šest bastiona. Bedemi Velikog Grada su dodatno ojačani oko 1818. za vreme vladavine sultana Mahmuda II kada Turci drugi put osvajaju Fetislam. Tada su iznad glavnih ulaza u tvrđavu – Dunavske, Orospi i Varoš kapije postavljeni počasni natpisi kojima se veliča Mahmud II. U unutrašnjosti Fetislama pronađeni su objekti i građevine namenjeni posadi tvrđave kao što su baratuna, magacini, hamam, lagumi, džamija. U rukama Osmanlija Fetislam je do 1867. godine, kada je sa još šest gradova, predat knezu Mihailu i tada su Turci definitivno napustili ove prostore.