在一間私立偵探事務所擔任助手的阿渡（ワタル）與阿曆（コヨミ）面前，某天來自1000年後未來的兩人遠親後代——卡蓮公主（カレン姫），搭乘時光機現身。她是未來地球「南達拉王國（ナンダーラ王国）」的公主，但由於身為國王的父親過世，必須決定下一任國王的人選。
然而，要繼承南達拉王國王位（ナンダーラ王位），必須找到並捕捉象徵王位繼承、能夠穿越時空的神鳥朱雀（ジュジャク）。為此，卡蓮公主（カレン姫）前來請求兩人協助尋找朱雀（ジュジャク）。
不過，覬覦南達拉王國王位的並不只有她一方。還有另一勢力——因過度行賄而沒落的斯卡普拉王朝（スカプラ王朝）末裔米蓮喬（ミレンジョ）及其一夥人。米蓮喬（ミレンジョ）企圖讓弟弟小麻呂王子（コマロ王子）登上南達拉王國王位（ナンダーラ王位）以獲取龐大財富，甚至打算藉此奪取整個王國。
在旅途的各個地點，米蓮喬公主一行人（ミレンジョ姫一味）不斷派出機械兵器，妨礙卡蓮公主一行人（カレン姫一行），試圖搶先奪得朱雀（ジュジャク）。阿渡（ワタル）則從卡蓮（カレン）那裡獲得變身為「終於登場俠（ヤットデタマン）」的力量，與擁有自我意識的巨大機器人大巨神並肩作戰，一次次擊退米蓮喬等人的陰謀。
