Početkom 15. i u tijeku 16. stoljeća pred osmanlijskom silom padaju carstva i kraljevstva što je imalo za posljedicu pripremanje za obranu u još neosvojenim dijelovima Europe. Dramatično razdoblje za Europu i za gradnju utvrda nastupilo je nakon 1453. godine i pada Carigrada. Ubrzo nakon tog događaja Osmanlije su pod zidinama Senja zbog čega tadašnje vojne, civilne i crkvene vlasti trebaju vrlo brzo organizirati obranu grada i stanovništva.
U interesu što bolje obrane 1539. godine Ivan Lenković postaje senjskim kapetanom te kao iskusan vojskovođa i dobar poznavatelj tadašnjih utvrđenja na terenu uviđa potrebu izgraditi utvrdu koja će uspješno odolijevati modernom artiljerijskom naoružanju. Pismom obavještava cara Ferdinanda I. o stanju senjskih bedema i utvrda naglašavajući potrebu pojačanja obrane Senja i zalaže se za gradnju jedne moderne i snažne tvrđave na obližnjem brdu.
Kada je 1551. carski dvor osigurao sredstva, započeo je Lenković na 62 metra visokom brdu Nehaj graditi dugo željenu tvrđavu „fortecu“. Odobrenjem vojnih i crkvenih vlasti Lenković je za izgradnju dao porušiti sve zgrade izvan gradskih bedema i od obrađenog kamena iz ruševina sagradio je do 1558. jednu od najsnažnijih ali i najljepših tvrđava onoga vremena. O upotrebi materijala srušenih objekata svjedoče brojni kameni spomenici – spolije (natpisi, reljefi te profilirani nadprozornici i nadvratnici) od kojih je dio vidljiv u zidovima tvrđave, a dio izložen u prizemlju. Tvrđava ima kockasti oblik i orijentirana je prema stranama svijeta. Široka je 23,50 m, a visoka 18 m.
Procijenjeno je da je u Tvrđavu ugrađeno preko 3400 m3 materijala. Ako uzmemo da je građa Nehaja teška 2,2 t po 1 m3, može se zaključiti da je u Nehaj ugrađeno gotovo 7500 t kamena, pijeska i vapna. Kad je riječ o kamenim fasadama Nehaja u njima se jasno zapažaju, po prilici na trećinama gradnje, tri različite vrste kamene građe: u najdonjem sloju je lokalni kraški vapnenac, zatim razgrađeni samostanski pravilno tesani kamen, a najviši sloj je izmiješan i sastoji se od više različitih vrsta i oblika kamena.
Debljina zidova Tvrđave iznosi 3,20 m u prizemlju koji se prema vrhu suzuje na 2,50 m a završavaju s kruništem na kojem je pet malih ugaonih kula. U zidinama se nalazi oko stotinu puškarnica i jedanaest velikih otvora za topove. U Tvrđavu se ulazilo stepeništem preko drvenog mosta kroz dvoja vrata.
Njezinom izgradnjom znatno je pojačana obrana grada Senja i Primorja od prijeteće osmanlijske i mletačke opasnosti, a u slučaju topovske vatre zaustavljanje napadača na većoj udaljenosti.
Sagrađenu utvrdu trebalo je opskrbiti ljudstvom i hranom što je bila obveza organizatora obrane grada. Osmanlijskim napredovanjem prema zapadu, a posebice nakon pada Klisa 1537. godine, povećava se opasnost za grad Senj koji postaje utočište i uporište prebjezima nazvanim uskocima, koji se odmah uključuju u obranu i postaju stalna posada senjske obrane i tvrđave Nehaj.
Iz Lenkovićevog izvještaja iz 1563. godine saznajemo da je kaštel i grad Senj uključujući i novu utvrdu iznad grada branilo 300 ljudi. Bili su to dakako uskoci pod komandom generala Ivana Lenkovića koji su utvrdi dali ime Nehaj. Ovaj naziv označava kako oni ne mare, ne haju za opasnost što je u narodnoj predaji povezano i s mnogim junačkim djelima uskoka.
U cilju obrane od Osmanlija 1469. godine osnovana je Senjska kapetanija, kasnije Primorska krajina koja čini jezgru buduće Vojne krajine. Neki od senjskih kapetana bili su znamenite i slavne ličnosti.
