У Паланзі знаходився храм головного божества жемайтійських племен, Праужиме (Praamžimas). Це божество було жіночою версією фаталістичного божества долі та необхідності, яке називалося - згідно з Крашевським – "Лаймою", коли воно означало зло, і "Лаккімас", коли воно означало добро. Цей культ припускав, що все, що існує - боги, люди, тварини і весь космос - керується невблаганним законом необхідності і кінцевої долі, від якої немає ні порятунку, ні втечі, а його матеріальною проекцією був священний вогонь. Так звані жертвенні вогні, що були вівтарями, горіли в багатьох місцях Жемайтії; казали, що їхній попіл мав чудодійну цілющу силу, їхнє полум’я використовувалося для ворожінь і завдяки їм шукали правду, їхнє гасіння передвіщало катастрофу чи катаклізм — тих, хто відповідальний за гасіння багаття, спалювали на вогнищі. Найважливіше зі священних багать палало на прибережній горі в Паланзі, постійно підтримуване жемайтійськими вайделотками, жрицями, які пообіцяли зберігати цнотливість під страхом бути спаленими, похованими живими або втопленими в річці.
Кейстут побачив у Паланзі найвродливішу з вайделоток, доньку могутнього жемайта Відімунда, знамениту Біруту. Про її красу ходили не менш захоплюючі легенди, як і про освіченість Кейстута (він володів кількома мовами), його мужність, чесність і щастя. Чудовий історик Юліан Клячко пише в "Унії Польщі з Литвою":
"
Клячко описує постать Кейстута реченнями, повними слів честь і похідних: "
Третьою його любов'ю була Бірута. Володар Жемайтії, Трок (Тракаю), Підляшшя та Полісся збожеволів від кохання з першого погляду й порушив священні закони свого народу, викравши діву, віддану божеству.
Першу ніч вони провели в глибині лісу. Коли князь підійшов до її хатини, Бырута стала біля входу з ножем у руці. Коли він зробив ще один крок уперед, вона притулила кінчик леза собі до шиї. Вони стояли один навпроти одного, мовчазно дивлячись один одному в очі, оточені переляканими воїнами, одному з яких раніше довелося дати вайделотці ніж, щоб та захистила себе та Кейстута від помсти Праужиме. Тоді князь сказав щось пошепки, що ніхто не почув, і її рука впала, і Бірута відступила в хатину. Кейстут пішов за нею. Коли вранці вони сіли на коней, вона вже не була вайделоткою, а він уже не був дикуном. Вони обоє були закохані.