バルカン星でスポックの肉体と精神を融合させたクルーは、軍法会議を覚悟してクリンゴン艦で地球に向けて出発しました。そのころ、地球に向けて巨大な宇宙船が解読不能の信号を発しながら近づいていました。こちらからの呼びかけにはまったく応答せず、近辺の宇宙船やステーションは謎の宇宙船が通り過ぎただけでまったく制御できなくなっていました。
ついに地球に到達した宇宙船は信号を出し続け、海水を巻き上げて地球全体を雲で覆ってしまい、地球連邦政府は惑星遭難信号を発信します。カークたちは謎の信号が探査のために海に向けて発せられていることから、それが21世紀に絶滅したザトウクジラの鳴き声だと気がつきます。
地球を救うには生きたザトウクジラが必要と考えたカークは、太陽周回加速によるタイム・スリップで20世紀末のアメリカに向かいました。クルーたちはサンフランシスコの街に出て、クジラを探すカークとスポック、そのクジラを運搬するための巨大水槽を手に入れるマッイとスコット、そして帰りのエネルギーを確保するために原子力空母に潜入するチェコフとウフーラの三組に分かれ、それぞれが時代のギャップで四苦八苦するのです。
カークはクジラ博物館のジリアン(キャサリン・ヒックス)と知り合い、飼育されている2頭のザトウクジラが、近日中に研究のために発信機を取り付けたうえでアラスカで放流されることを知ります。しかし、何とも怪しげな行動をとるカークとスポックを警戒して、ジリアンは発信機の周波数を教えようとはしません。
しかし、ジリアンに内緒で夜のうちにクジラたちは放流されてしまい、このままでは捕鯨の餌食になる危険もあるため、ジリアンはカークたちがクジラを救ってくれることを願って周波数を教えます。そして、彼らが未来から来たことも理解して、未来でクジラの世話をするため一緒に乗船するのでした。
クジラを発見したカーク達は、船内に転送することに成功し、再び時間の壁を打ち破り彼らの現代に戻りました。海に放たれたクジラは宇宙船の信号に反応して鳴き声を上げ、それを確認した宇宙船は再び宇宙の彼方に去っていきました。クルー達はこの功績により赦免されますが、カークだけは階級格下げで提督から大佐となり、艦長勤務を命じられます。乗船を命じられたのは、新たに再建されたエンタープライズ号でした。
タイム・スリップによる哲学的な命題は、ここではあまり考えていません。彼らからすれば、すでに決定した未来であって今更変わらないとマッコイの台詞で片付けています。あくまでもエンターテイメントですからそれでかまわない。細かいことを考えると、シリアスな展開になって、せっかくのコメディ・タッチが台無しになってしまいます。
もともとテレビ・シリーズでも、社会風刺が効いたストーリーを取り上げていたのですが、当然ここでは絶滅の危機に瀕しているクジラに対する捕鯨という問題が中心テーマですが、コメディをかませて堅苦しくしなかったところはうまい。登場するザトウクジラが見事に撮影されているので、反捕鯨団体からは何か無理強いする仕掛けがあったのでは抗議されたらしいのですが、実はこれは正確に作られたアニマトロニクス技術によるロボットだそうです。
最後に登場する新しいエンタープライズ号。船体番号はNCC-1701-Aとなっています「-A」が追加され、内部も白いカーブした壁で統一され、新しさを強調していました。そして彼らの冒険は続くのです。