राजुली और मालूशाही के बारे में कई दंतकथाएं प्रचलित हैं | सबसे अधिक प्रचलित तो यही कथा है कि दोनों राज परिवार के थे और जब ये दोनों अपनी माँ के गर्व में थे तब दोनों राजाओं ने यह कहकर रिश्ता पक्का कर दिया था कि यदि एक का लड़का और एक की लड़की होगी तो इनकी शादी कर हम समन्धी बन जायेंगे | किन्तु एक और कथा भी प्रचलित है जिसमे कहा गया है कि राजुली बहुत ही गरीब घर की लड़की थी और उसके परिवार वाले भेड़ पालक थे| यही इनका जीविका का साधन था | राजुली बहुत ही खूबसूरत कन्या थी जिसकी खूबसूरती के बारे में राजा मालूशाही ने भी सुन रखा था किन्तु उसे कभी देखा नहीं था | एक दिन राजुली अपनी माँ से पूछती है कि हमारे देश में सबसे श्रेष्ठ, सुन्दर और शक्तिशाली राजा कौन है ? उसकी माँ उसे बतलाती है कि ऐसा राजा केवल मालूशाही है |ऐसा सुनकर उसके मन में मालूशाही के प्रति प्यार उमड़ पड़ता है और वह मन ही मन सोचती है कि एक बार वह राजधानी जाकर मालूशाही को अवश्य देखेगी | एक बार उसके पिता राजधानी जाने की बात करते हैं तो वह भी जिद कर शहर आती है और ईश्वर की कृपा से उसकी मुलाक़ात राजा मालूशाही से हो जाती है |