Uz prekrasan, malen srednjovjekovni grad/utvrdu vezano je bezbroj legendi.
U tvrđavi, prema predaji, živi ogromna i opaka zmija. Tijekom Drugog svjetskog rata, jedan je oficir zatvorio vojnika u podrum Sokolca jer je zaspao na straži. Odjednom se iz podruma začuo vrisak: “Kača! Kača!” Kad se vojnik više nije oglašavao, oficir je sišao da vidi što se događa. U podrumu nije bilo vojnika – samo ogromna zmija. Priča se da se oficir, iz grižnje savjesti, kasnije sam ustrijelio.
Na putu prema utvrdi nalazi se kamen veličine djeteta. Legenda kaže da je tijekom napada Turaka na utvrdu mlada princeza u dvorcu preminula, a zbog ratnog kaosa nitko to nije primijetio. Jedan je čovjek pronašao njezino tijelo, iskopao grob, položio princezu i na grob stavio veliki kamen. Nedugo zatim poginuo je u borbi s Turcima. Nitko nikada nije saznao gdje je princeza pokopana.
Priča se i da se ispod Sokolca nalaze brojni tuneli. Na mjestu gdje tlo odzvanja šuplje kada se po njemu udari, vjeruje se da se nalazi rimska pivnica u kojoj je skriveno veliko blago.
Baba Rajkovićka ostala je upamćena kao junakinja koja je obranila Sokolac polijevajući kipuću juhu po Turcima tijekom opsade. Druga baka, nakon što su Turci pobili svu posadu, ostala je sama u gradu sa svojom kozom. Noću je postavila kolce po bedemima i na njih ogrnula vojnička odijela. Ujutro su Turci, vidjevši što su mislili da je nova vojska, napustili opsadu. Baka je sačuvala i grad i svoju kozu, koju je puštala niz bedeme da se nabrsti sa stabla bazge.