Noong unang panahon sa Mindanao, may isang mangingisda na may anak na dalagang nagngangalang Waling-Waling. Si Waling-Waling ay kilala sa buong nayon dahil sa kanyang pambihirang ganda at kabutihang-loob. Dahil sa kanyang kagandahan, naging usap-usapan siya hanggang sa makarating ang balita sa makapangyarihang si Rajah Solaiman. Nabalitaan ng Rajah ang tungkol sa dalaga at nais niya itong makita at angkinin.
Nang mabalitaan ng ama ni Waling-Waling ang masamang balak ng Rajah, labis siyang nag-alala para sa kaligtasan ng kanyang anak. Upang mailayo si Waling-Waling sa atensyon ng makapangyarihang pinuno, nagpasya ang ama na dalhin ang dalaga sa pinakamalalim at pinakasikretong bahagi ng gubat. Doon, itinago niya ang anak sa loob ng isang kuweba na napapalibutan ng makakapal na puno at mga baging.
Sa loob ng mahabang panahon, namuhay si Waling-Waling sa gubat nang mag-isa. Kinakailangan niyang manatiling tahimik at hindi magpakita sa sinuman upang hindi siya matagpuan ng mga tauhan ng Rajah. Ang tanging naging kasama niya ay ang mga ibon, paru-paro, at ang mga ligaw na halaman sa paligid.
Ngunit hindi nagtagal, natunton din ng mga kawal ni Rajah Solaiman ang kinaroroonan ng dalaga. Nang maramdaman ni Waling-Waling na malapit na ang mga kawal, nanalangin siya nang taimtim sa mga diwata ng kagubatan. Humiling siya na sana ay hindi na siya mahanap ng Rajah at manatili na lamang siyang ligtas sa piling ng kalikasan.
Habang papalapit ang mga kawal, unti-unting nagbago ang anyo ni Waling-Waling. Ang kanyang balat ay naging makinis na talulot, ang kanyang buhok ay naging mga dahon, at ang kanyang buong katawan ay unti-unting naglaho hanggang sa siya ay maging isang napakagandang bulaklak na nakakapit sa mga sanga ng puno.
Nang dumating ang mga kawal sa lugar, wala silang nakitang dalaga. Ang tanging nakita nila ay isang kakaiba at napakagandang orkidya na hindi pa nila nakikita noon. Dahil sa ganda nito, tinawag nila itong Waling-Waling bilang pag-alaala sa dalagang naglaho.
Hanggang sa kasalukuyan, ang Waling-Waling ay itinuturing na reyna ng mga bulaklak sa Pilipinas. Ito ay nagsisilbing paalala ng isang dalagang piniling maging bahagi ng kalikasan kaysa maging bihag ng isang makapangyarihang hari.