Tvrđava je izgrađena 1538. od strane Španaca kada su flote admirala Andrea Dorije stigle u Herceg Novi u junu te godine, i prvobitno je nazvana po rimskom caru Karlu V. Ime koje nosi danas duguje lokalnom stanovništvu. Samo godinu dana posle toga, Turci su ponovo osvojili grad vođeni svojim admiralom Hajredinom Barbarosom, koji je poveo ogromnu flotu u jako tešku i iscrpljujuću bitku. Turci su ponovo izgradili tvrđavu između 1539.-1548., na istom mjestu gdje su je prvobitno sagradili Španci koji su na tom mjestu prije toga uništili jednu manju tursku naseobinu. Turci su ostavili pisani testament, na turskom (oni su do 1928. godine koristili arapski jezik, a posle toga prešli na latinicu) o izgradnji ove tvrđave koje je bilo postavljeno iznad ulaza i na kojem je pisalo: „Ovu tvrđavu, po naredbi sultana, je izgradio Sulejman, sin velikog Emira Selmana Hana, moćnog viteza, čiji brat Sinan-beg, koji je bio veliki vezir sultanov. Neka poživi dugo, i napreduje u sreći i bogatstvu pod zaštotom i pomoći milosrdnog Boga. A pjesnici koje put ovuda nanese, neka bi gledajući me, zanosno kliktali: o krasna ti si, divna zgrado“ Zbog strateške prednosti brda Bajer, tvrđava Španjola je locirana na sjeveroistočnoj strani grada na nadmorskoj visini od 170m i dominira ulazom u Bokokotorski zaliv, i pruža savršen vidikovac okolnog područja. Tvrđava je fortifikovana sa ogromnim zidinama i 4 cirkularna bastiona na svakom uglu. Iako izvana izgleda impresivno, iznutra je vrlo malo ostalo. Glavni ulaz je na istočnoj strani i obezbjeđen sa vanjskim zidom dok je južna strana okrenuta moru, pretrpjela nekoliko adaptacija za nove fortifikacione standarde (znak Mlečana) dok je na zapadnoj strani ostala turska arhitektura i djelovi džamije. Španjola je uvijek imala karakter defanzivne tvrđave sve do početka 20. vijeka. U drugom svjetskom ratu je bila korišćena kao zatvor. U nekoj tački, svaki vladar je pravio neke modifikacije na tvrđavi. Mlečani su na primjer izgradili veliki polukružni zid između dva bastiona stvarajući tako unutrašnje dvorište. Takođe su postavili i drugo stepenište do zidina tvrđave i na taj način pomakli ulaz i pretvorili tursku džamiju u baraku. Austrougari su takođe napravili par izmjena u skladu sa svojim potrebama, koje su na kraju ispale nove strukture pored same tvrđave. Tvrđava je povezana sa podzemnim prolazima sa druge dvije tvrđave u gradu, Kanli Kulom i Forte Mare. Danas su ti prolazi više manje uništeni, ali u prošlosti, kada su bili u potpunosti funkcionalni, pružali su značajnu stratešku prednost zato što bi odbrambene snage grada, čak i u slučaju pada Kanli Kule i Forte mare, mogli jednostavno da se presele na Španjolu i nastave odbranu odatle.