私立探偵事務所で助手として働くワタルとコヨミのもとに、1000年後の未来から一人の王女が現れる。彼女の名はカレン姫。実は彼女は、ワタルとコヨミの遠い子孫であり、未来の地球に存在するナンダーラ王国の王女であった。
カレン姫は、国王である父の死により、次期国王を決める必要が生じたことを告げる。しかしナンダーラの王位に就くためには、王位継承の証である「時空を越えることのできる鳥・ジュジャク」を探し出し、捕まえなければならない。彼女は、そのためにワタルとコヨミの助力を求めて現代へとやって来たのだった。
だが、ナンダーラ王位を狙っているのはカレン姫だけではなかった。スカプラ王朝の末裔であり、かつて賄賂の乱用により没落したミレンジョとその一味もまた、弟のコマロ王子を王位に就けて莫大な富と権力を手に入れようと目論んでいた。
ジュジャクをめぐる旅の道中、ミレンジョ一味は次々とメカを繰り出してカレン姫たちの行く手を阻み、ジュジャクを奪おうとする。しかし、ワタルはカレンから「ヤットデタマン」の力を授かり、自意識を持つ巨大ロボット・大巨神と共に、ミレンジョ一味の悪だくみを打ち砕いていくのだった。
