Iako danas nema sumnje da je Hercegovina dobila svoje ime po hercegu Stjepanu Vukčiću, koji je taj naslov dobio 1448. godine, narodno predanje o nazivu Hercegovine je nešto drugačije. Ostala je zabilježena jedna anegdota iz austrougarskog perioda, koju prenosi jedan Bošnjak iz Mostara u razgovoru sa novinarom Ivanom Zovkom, o objašnjenju ovog naziva.
“Čim je Bosna i Hercegovina, Bog ti pomogao, bila fet učinjena (pokorena) od Turčina, odmah nizami (vojnici) stanu iskati izun (dopust), da odu malo u svoj vilajet (državu) na selamluk i na tevdil havu (hlađenje), biva da malo promijene hariju (zrak), jer nikako nijesu mogli obiknuti našu vrućinu i žegu. Mnogi od njih, koji nijesu bili više godina kod kuće, dobiju teskeru (putnicu), da mogu ići. Kad su došli tamo u svoju domovinu, već otkle je koji bio, stanu ih zapitkivati njihove emšerije (poznanici) i jarani o svem i svačem i kakva je ta gjaurska (zapadnjačka) zemlja i kakvi su kauri. Oni im počnu svašta pričati, a od Hercegovine im još reknu nabaška (posebice), kao da su se svi sto godina zdogovorili i ovo: ‘Para jok, herseng čok’, što biva, efendum, po naški: ‘Para nema, a kamenja bukadar (i odviše)’. O tome začuje polagano i sultan u Stambolu, pa sabere na divan (vijeće) sve svoje mušire, valije i vezire (razni dostojanstvenici u Osmanskom carstvu), te ih zapita kako će novo ime nadjeti toj građanskoj zemlji u za inat gjaurima, jer mu je dosta askera (vojnika) pozobala, dok ju je zauzeo. Na to se digne jedan stari paša, koji je bio na Hercegovini, kako bi bilo baskin (zgodno) po onoj nizamskoj “herseng” – ‘puno kamenja’ – nadjenuti ime i cijeloj zemlji, jer ima i onako plaho puno kamenja. Sultan i divan na to kail i raži bude (privoli), te po askerskoj riječi ‘herseng’ prozovu zemlju Hersengovina, odakle joj poslije došlo ime Hercegovina”.
