Kazuje se da su Pale dobile ime po Pavlovićima. Rodonačelnik ove porodice bijaše Radin Jablanić, otac bosanskog kneza Pavla Radinovića, koji izgubi glavu u uroti skovanoj u dugogodišnjim intrigama i sukobima rusaške gospode, koja se naprosto pomami nakon smrti kralja Tvrtka I pa bez njene naklonosti ni jedan Kotromanić ne mogaše sjesti na bosanski prijestol.
Skasapiše ga i glavu mu, kao dokaz dobro obavljena posla, odrubiše katili nahuškani od kralja Ostoje i drugog rusaškog gospodina Sandalja Hranića, sina Hrana Vukovića, koji opet bijaše brat Vlatka Vukovića – onog Vlatka koji u čuvenom boju na Kosovu polju jahaše lijevim krilom na čelu Bošnjana – a u toj uroti, priča se, učestvovao je i Vukmir Zlatonosović, vlastelin čija se plemenita stjeraše oko Usore i Soli i do Dramešine i Drine i međiše sa zemljama Pavlovića. Bogumil Vlatko Tumurlić, koji godinama služiše na Pavlovom dvoru, prenese njegovo obezglavljeno tijelo i sahrani ga na brdu s druge strane Trebevića, koje narod prozva Pavlovac – na njemu je od stotine stećaka pod kojima ležahu Pavlovići ostao samo jedan, gorostasni sljemenjak za kojeg mnogi tvrde da je obilježavao grob umorenog Pavla Radinovića.
Kažu ozbiljni historičari da je Pavlovića zemlja počinjala ponad Vrhbosne. Stjeraše se ona dolinom rijeke Prače sve do Drine i širiše se na sjever, kroz Borač do Soli, i na jug, do zemlje Hranića. U Pavloviće zemlje ulazilo se dolinom Miljacke pa stoga Pavlovići klisure ponad nje načičkaše utvrdama s kojih štitiše kapije svoje plemenite. Pored mitskog grada Hodidjeda, za koji mnogi kazuju da je u njemu stolovao did, poglavar Crkve bosanske, pa je zbog toga i dobio tako neobično ime, nad klancem kojim se ulazilo u Pavlovića posjede čučala su još dva dobro utvrđena grada – onaj na Bulozima, bezimeni, i ovaj ovdje, ponad samog izvora Palanjske Miljacke koji već stoljećima raspiruje maštu naroda podno triju planina, Romanije, Jahorine i Trebevića, i kojeg prosto zovu Gradina.
Sve to davalo je prostoru ponad Vrhbosne obol magičnosti, a pogotovo u pričama koje su se širile po dalekim krajevima: kako onamo, iza romanijskih magli, ima takva zemlja po kojoj plaza trikleta Jerina i takav grad kojeg zovu Hodidjed. Prostu i poštenu čovjeku ovuda nije bivalo milo prolaziti i na to ga je mogla navratiti samo ljuta nevolja. Zato Osmanlije ovom mjestu nadjenuše ime Bogazi Yumru – Nabreklo Grlo, a službeno, u defterima cijeli kraj nazivahu Pavlovića zemlja, odnosno Pavli vilajet. Tako se ovaj naziv iz usta službenika prenese na narod te ga svi počeše zvati Pavli zemljom. Kako su desetljeća prolazila, ono “zemlja” otpade, jer narod je bosanski u svom govoru uvijek volio da se posluži kraticom, a pogotovo u predjelima planinskim.
Tako su ga sve češće zvali Pavli, a vremenom i ovo “v”, oko kojeg se jezik silno lomiše, ispade samo od sebe poput mliječnjaka i ostade samo Pali. To nije moglo dugo trajati jer nije imalo roda, pa ljudi ostajahu zbunjeni svaki put kada izgovarahu Pali izvan prvog padežnog oblika. Na kaju pređe “i” u “e” i dobismo Pale; u međuvremenu narod smetnu s uma Pavloviće i silna ih stoljeća odnesoše u zaborav.
Legende pričaju drugačije. Pošto se u narodnoj svijesti nije održalo ništa od bosanskih plemenitaša Pavlovića, čije prezime i danas nose neke paljanske porodice, u njoj ne osta utisnuto ko tačno izgradi ovaj grad: Grci ili neko drugi, ali narodno predanje vrlo dobro pamti kako ga Osmanlije osvojiše na prevaru. Kao i u mnogim legendama, koje se raspinjahu Bosnom, narod je dramatiku gradio gomilajući silnu vojsku pod bedeme. Tako i ovdje, janjičari danima nahrtahu na ovu tvrđu, ali joj ništa ne mogaše, ni topovima, ni lumbardama, a lagumdžije bijahu nemoćne – od tvrdoglavog kamena koji bi se pojavljivao čim ašovom udariš u zemlju ni mišija rupa, da prostiš, nije se mogla iskopati.
Kao i u tolikim drugim primjerima, ne bi Osmanlije ni osvojile Gradinu da se ne nađe izdajnik. Umjesto pogrbljene starice, koja savjetovaše sultana da zabereči cjevovode kojima se grad snabdijeva vodom, ovdje se pojavljuje muškarac, i to mladić. Narodni bijes prema ovom izdajniku bijaše toliki da nije popuštao stoljećima. Prođe četiri i po stoljeća, a narod, jednakom gorčinom, spominjaše njegova imena i obasipaše ga kletvama. Eto, prije više od sto godina, 1894. godine, kada Božidar Čerović objavi ovu legendu u Bosanskoj vili, Paljani se sjećahu Staniše i ispričaše mu kako, vidjevši koliko se muče, obeća on Turcima da će im k’o od šale predati grad. Reče im Staniša da se ništa ne sekiraju, samo da sačekaju noć i da će iste večeri biti s one strane gradskih bedema.
Osmanski zapovjednici gledahu ga s čuđenjem i činilo se da će ga prije posjeći nego da mu povjeruju. Ali, nakon dugog vijećanja, zaključiše da nemaju šta izgubiti, ionako su mislili ponovo nahrnuti tek prekosutra kada im stigne još buljuka. Tada pozvaše Stanišu, kojeg bijahu svezali, misleći da je riječ o kakvom uhodi i špijunu, koji ih nastoji nagovoriti na zlo pa da svi izginu. Posadiše ga uvrh sofre i izredaše ispred njega svakojaka jela i ugostiše ga baš onako kako to samo Turčin zna. Staniša im usred zalogaja reče da narede vojsci da skupi što više drveća, i javora, i šmreke, i bukve, i hrasta, svega. Osmanlije ga gledaše zbunjeno, a neki zakretaše glave ne mogavši gledati kako Staniša halapljivo trga komade pečenja i kako mu hrana ispada iz usta. Glavni među njima reče da ništa ne zakreću pogleda i da, ako su već s ludim Stanišom došli do ove tačke, sad uzmaka nema, makar im se i stotine puta činio benest i da se sprda s njima i da sve ovo radi samo da bi se čestito najeo. I glavni naredi dvojici da postupe baš onako kako im je Staniša rekao, a tolmaku da nastavi prevoditi ono što Staniša kaže. Ali ovaj samo šutaše i s još većom halapljivošću navali na jela ispred sebe.
Staniša opet progovori tek u akšam. Reče da sada svaki vojnik od onog skupljenog drveća naloži po deset vatri, a razmak između njih da bude deset koraka i da budu u deset redova i deset vrsta i da oko svake vatre usprave deset smreki. Snebivajući se i nevoljko, osmanski zapovjednici poslušaše i ovo i u obliku naređenja prenesoše na vojsku. Tad Staniša zatraži da ide na kapije grada i da traži od kaštelana da ga pusti unutra. Osmanlije mu u prvi mah ne dozvoliše, sluteći kako u njegovom planu leži neka velika zamka koja će ih sviju povući u strašnu pogibelj. Opet narediše da ga svežu i opet sjedoše da vijećaju i da sa svih strana zaviruju u Stanišine prijedloge.
U ponoć svijećaše da im ničim ne može nauditi pa ga pustiše neka ide na kapije grada. Očekivali su da će ga njegovi s bedema zasuti strijelama uvjereni da je osmanska uhoda. Ali, na opće zaprepaštenje, vidješe kako se kapije grada otškrinuše i iza njih sasvim mirno, s glavom na ramenu, zamače ludi Staniša. Dok su gledali kako nestaje iza vrata, učini im se da su shvatili njegove nakane, jer tek tada im se one smreke poredane oko vatri učiniše kao zasjednute ljudske figure. Kako li tek stvarno izgledaju onima s bedema? U trenutku dok su zapanjene Osmanlije postavljale sebi ovakva pitanja, zapovjednik grada u pratnji Staniše i svojih posilnih posmatrao je hiljade vatri pred sobom i oko svake po deset vojnika. U njemu se kotio strah.
Staniša pričeka da mu se, uslijed straha, počnu trzati mišići na licu te mu tada reče da je najbolje da se odmah preda. Kad ujutro, reče mu Staniša, onolika vojska nahrne na bedeme, neće ni kamen na kamenu ostati, a njegova glava skotrljat će se do Vrhbosne. Šta će, zapovjednik naredi vojsci da položi oružje i otvori kapije grada. Ostade on ščuđen kada vidje kako janjičari uzimaju one ljude kao da su od perja i nadnose ih na plamen i tada, po mirisu zapaljene smrekovine, spoznade da je prevaren i da je grad mogao odbraniti, ali već bijaše okovan u lance i janjičari ga vodiše pored Staniše te mu on svom silinom svoga prezira pljunu u lice.
Još ga je uspio upitati koliko su ga Turci platili, ali od vriske janjičara koji su sada stajali na bedemima, umjesto njegovih vojnika, i svaki u ruci držao zapaljenu smreku, nije čuo odgovora. Po tim vatrama i toj paljevini ovo mjesto dobi naziv Pale, da ih vječito opominje na izdajnika Stanišu. Njemu sultan kao nagradu darova Čelinu i još jedno selo podno Trebevića, Dovliće, koje ime dobi jer Osmanlije na tom mjestu učiniše pobjedonosnu dovu. Ali Bog bi pravedan. On vrati milo za drago Staniši i navrati đavola da mu ponese imetak. Otad ostadoše njegovi potomci gola sirotinja i narod ih prozva Golići. Eno ih u Čelini, krepaju od gladi.
Sasvim zanemarujući Pavloviće, narodna predanja pripisuju paljansku Gradinu prokletoj Jerini. Kazivahu da ona nekada davno ozida ovaj grad, kao što je zidala i Smederevo, i da poslije godinama vladaše ovim krajem. Kazuju da je bila nezasita. Svakog dana birala je drugog ljubavnika, po cijelu noć ga iscrpljivala i čula se vriska, a ujutro sluge ga iznosiše obezglavljenog. Zato su, kada bi se u nekom selu pojavili stražari s crnim zastavama na kopljima, svi bježali i sakrivali stasale muškarce po pećinama, da ih ne vode Jerini u krevet. Vladala je surovo, ukivajući ljudima strah u kosti. Izgradila je veliku beraču na Prači i prijetila da će, samo ako se ko drzne pa se pobuni ili i riječ izusti protiv njenog vladanja, potopiti cijeli kraj, od Stambolčića do Hrenovice.
Legenda kaže da je prokleta Jerina sagradila i tvrđavu na Bulozima kod sela Odiđeda. Za izgradnju tog grada svaka muška glava morala je dati tri litre zlata. Kažu da je silno zlato ostalo pod zemljom i da onaj ko ima neiskvareno oko, koje nisu doticali uroci i čije misli nije milovalo zlo, dođe li ovamo uoči Blagovijesti, kada se nebo tri puta otvara, vidjet će kako iz zemlje izbija modar plamen. To progovara davno zakopano blago, ono se javlja da iskuša probrane, pa ko mu odoli, cijelog će mu života gorjeti svjetlost i neće mu dati da skrene s puta istine i pravde, ne odoli li, jao se njemu, niko ne zna šta ga čeka. Na ovo predanje nadovezuje se priča kako su za vrijeme Omer-paše Latasa nekakvi znatiželjni izletnici nabili top zaostao u tvrđavi, a kada je eksplodirao, izbaci iz zemlje ćup dukata i rasuše se po cijelim Palama.
Prokletu Jerinu iz narodnih predanja historija predstavi u liku Mare Branković, bake bosanske kraljice Mare. O njoj se piše da je rođena pod imenom Irina, u poznatoj grčkoj porodici Kantakuzin, koju proslavi Jovan VI, njen pradjed, kada se uz pomoć Osmanlija pope na bizantijski prijestol, a kao zalog savezništvu udade kćer Teodoru za sultana Orhana, sina Osmanova. Bila je supruga srpskog despota Đurđa Brankovića prozvanog Smederevac, jer je nakon gubitka Beograda dao izgraditi novu predstojnicu na Dunavu, i to u kratkom roku, te su zbog toga na narod bačeni nesnošljivi porezi i daće, a sve poslove oko izgradnje Smedereva, kazuje se, vodio je brat njegove supruge, Grk, pa otud svu krivicu za svoje patnje narod baci na Jerinu i prokle je za sva vremena.
A njoj, Irini, činjaše se kao da se sve ponavlja, jer se i njen muž Đurađ u borbi protiv ujaka Stefana osloni na Osmanlije, kao nekoć njen pradjed, i kćer Maru udade za Murata II. Đurđa zamijeni sin Lazar, ali taj umrije nakon dvije godine. Pošto ne ostavi iza sebe muškog potomstva, Lazareva supruga Jelena Paleolog dogovori s bosanskim kraljem Tomašem da njihovu najstariju kćer Jelenu udaju za njegovog sina Stjepana, posljednjeg bosanskog kralja i posljednjeg srpskog despota.
Izuzev predanja i narodnih priča, prokleta Jerina mogla je u Bosni biti samo u ljeto 1459. godine. Ime Jerina Branković pojavljuje se na spisku osoba koje su te godine izjahale na kapije Smedereva u pratnji Stjepana Tomaševića, koji grad predade Osmanlijama, i njegove supruge Jelene, koja je imala tek četrnaest godina i koju narod bosanski prozva Mara. Ako je to bila ona, a ne sestra kraljice Mare, onda je samo prošla sjeveroistočnim bosanskim trokutom. Poznato je da se kraljica Mara rastala s majkom čim su pregazili Drinu, te, noseći mošti svetog Luke, koje njen djed kupi od Osmanlija, produžila sa suprugom i njegovim stricem prema Bobovcu, a Jelena Paleolog i njena svita krenuše na sjever, pregaziše Savu i skrasiše se u zemlji njenih predaka.
Ali, po svoj prilici, ni od te bajke nema ništa. Mnogi historičari tvrde da je prokleta Jerina u vrijeme predaje Smedereva već drugu godinu bila s onu stranu života. Kazuje se da se nakon smrti muža Đurđa zamonašila i da je umrla u Rudniku kao monahinja. Oni koji joj ni u grobu ne dadoše mira pričaju da ju je otrovao sin Lazar, otac bosanske kraljice Mare, i to tako što joj salatu, umjesto sirćetom, poprska smrtonosnim otrovom.
