Poznat još i kao Vidoški Grad, srednjovjekovni Stolac je bio administrativno – teritorijalni centar župe Vidoš. Predpostavlja se da je nastao u VI stoljeću kada je bio jedan od limesa bizantskog cara Justinijana, koji je tekao sa juga preko Stoca i dalje na sjever prema Koštunu, Blagaju i Biogradu kod Konjica. U historijskim izvorima se javlja 1375. godine, a 1436. se spominje neki “Gojaković od Stoca do Vidoškog polja”.
Obzirom da je pored njega prolazio trgovački put iz Dubrovnika do Nevesinja, Blagaja i Dubrave, dubrovački izvori ga spominju 1444. godine kada je došlo do jedne pljačke dubrovačkih trgovaca. U povelji napuljskog kralja Alfonsa V od 19. februara 1444. i 1. juna 1454. godine spominje se kao posjed Stjepana Vukčića, a također i u povelji Fridrika III od 20. januara 1448. godine. Kao teritorij Vukčića spominje se i 13. juna 1465. godine. Tokom druge polovine XVII stoljeća više je puta napadan od strane Mlečana. Nakon Karlovačkog mira 1699. godine postaje sjedište kapetanije i više puta je popravljan. Dolaskom Austrougarske grad je više puta popravljen a izgrađena je i nova tvrđava.
Smatra se da je tokom cijelog perioda historije zadržao izvorni obim i forme, sa kastrumom na brijegu i bedemom opasanim podgrađem, utvrđenim zidovima i kulama koje se spuštaju prema rijeci Bregavi. Bedemi su dostizali debljinu i do 2 metra. Sa podgrađem obuhvata površinu od 2,7 hektara.
Tokom arheoloških istraživanja od strane Pavla Anđelića, utvrđeno je da je izgradnja obuhvatala više vremenskih faza. Tokom najstarije izgrađena je utvrda na najvišem, dosta ravnom, platou, uglavnom koristeći oblik zaravni. Prvoj fazi izgradnje pripada i pet bedema. Vjerovatno su na zapadnoj strani, tokom austrougarskog perioda, postojale još dvije kule sa uglovima. Grad je specifičan i po monolitnim blokovima koji su karakteristični za rimsko graditeljstvo, što ide u prilog rimskom periodu gradnje. Ipak, grad je pretrpio velika pregrađivanja u srednjem vijeku, a još više i za vrijeme osmanske uprave kada je Stolac, kao tvrđava, imao veliki značaj.
Zapadni dio utvrde je vjerovatno nastao u srednjem vijeku kao utvrđeno predgrađe, a koje je u osmanskom periodu ojačano novim tvrđavinskim elementima. Osmanlije su ovo mjesto pretvorile u kasabu koja se uskoro preselila izvan gradskih zidina i spustila se u dolinu rijeke Bregave, postajući na taj način čaršijom.
Vjeruje se da su Osmanlije glavne radove izveli u XVIII stoljeću. Kada je Evlija Ćelebija 1660. godine posjetio Stolac o tvrđavi nije zapisao niti riječi i pored činjenice da je u svakom mjestu koje je posjetio zapisao po nešto o tvrđavi. Na osnovu toga bi se moglo zaključiti da je grad bio zapušten i obnovljen tek u XVIII stoljeću. Gornji, istočni dio, bio je samo utvrda, a donji, zapadni dio, utvrda i prostor za stanovanje sa čaršijskim sokacima, kućama za stanovanje, džamijom za posadu i stanovnike utvrde, čatrnjama i cisternama. Kula broj VI, nazvana Dizdareva, bila je rezidencija dizdara i ima obilježje osmanskog arhitektonskog stila. Počevši od XVIII stoljeća u grad se ulazilo sa sjeverne strane. Husref Redžić ga smatra najstarijom kasnoantičkom/ranosrednjovjekovnom utvrdom u Bosni i Hercegovini.
