Kao i u slučaju drugih utvrđenja, ime grada pokušavaju da rasvetle različite legende. Jedna od popularnijih govori o prelepoj princezi Golubini. Ona je odbila nametljivo udvaranje turskog paše, pa je zbog toga vezana za stenu, koja je tačno naspram grada štrčala iz Dunava. Čekajući strašnu, očajničku smrt, Golubina se pokajala zbog svoje nesrećne odluke. Tako je kamen, na kom je izdahnula, nazvan Baba kaj, što na turskom jeziku znači Pokaj se!, dok je tvrđava ponela njeno romantično ime.

Postoje i verodostojnija predanja, poput onog po kojem je specifično ime grada odredio izgled kula na visokim liticama, sličnih elegantnim siluetama golubova. Zapamćene su i stare priče o beskrajnim jatima ovih ptica, koje su nekad živele na ovdašnjim stenama.

Izvor: Vuković i dr. 2017: Valentina Vuković, Srđan Ercegan, Vladimir Pihler i Miško Lazović, Tvrđave na Dunavu, Novi Sad – Beograd: „Prometej” – Prirodno-matematički fakultet – Radio-televizija Srbije, str. 147.