変わった形の宇宙船から一人の女がエンタープライズに乗り移り、スポックの頭脳を盗んで去る。24時間以内に元に戻さないとスポックは死ぬことになるため、カーク船長らはスポックの体を連れて頭脳探しに出かける。

エンタープライズはロミュラ帝国との間に設けられた中立ゾーンを通過し、ロミュラ領域を侵犯してしまった。これより数週間前からカーク船長が正確な判断を欠くようになっており、このロミュラ領域侵犯行為は、過労によるカーク船長のまれな過ちと思われた。そんな時、突如としてロミュラ宇宙艦隊が出現、エンタープライズを包囲する。

小惑星が衝突コースを接近、何らかの処置を講じなければ衝突によって破壊されるある惑星上に降り立ったカークたちは、そこにいた者たちの姿を見て驚く。その後カークは突如行方不明となるが、接近中の小惑星のコースを変えないと、衝突してこの惑星もろともカーク船長も飛び散るため、スポックは船長の捜索を一旦中止して小惑星に向けて飛び立つ。

惑星トリアカスから緊急連絡を受けたエンタープライズ。トリアカスに降り立ったカークたちが見たのは驚くべき光景、集団自殺だった。生き残っているのは子供たちだけ。しかも子供たちは親の悲劇を何も知らぬかの如く、楽しそうに遊びまわっているのだ。

エンタープライズは宇宙会議に出席したメデューサ大使を母星へ送り届ける任務を受ける。しかしメデューサ人は異形の種族で、人間が肉眼で見ると精神が錯乱する。そのために特別の容器に入っており、付き添いとして心理学者ミランダが同行していた。

エンタープライズはメルコト星の調査に向かった。いまだかつてメルコト星の生物と接触を持ったことのない地球連邦は、平和の使者としてエンタープライズを派遣したのだ。ところがエンタープライズの行く手にメルコト星人の宇宙ブイが立ちふさがり、直ちに引き返せと警告を与えてきた。

救難信号を受け、ある惑星に調査に赴いたカークは、住民の所在も襲撃の形跡も発見できなかった。そこに旧敵のクリンゴン船が現れるが、船は何者かに破壊され、エンタープライズの仕業と思い込んだ隊長のヤングはカークたちを捕虜にし、強制的に船に乗り込む。

マッコイが多血球血症であと1年の命だと知ったカーク船長がそれを司令部に報告しようとした矢先、小惑星そっくりの宇宙船にミサイル攻撃をかけられる。それが無人である有名惑星と衝突するコースを飛んでいると知ったカークはスポックと調査に赴くが、マッコイもたっての希望で同行する。

消息を絶ったパトロール船デファイアント号の救助に赴いたエンタープライズは、未知の空間でそれを発見する。スポック、マッコイ、チェコフの3人を率いたカーク船長は、デファイアントに乗り移るが、船内の乗組員はお互いに殺し合い、全員死亡していた。

救難信号を受け、ある惑星に赴いたカークとスポック、マッコイは、古代ギリシャ人そっくりの住民を見出して驚く。その王ペルマンは足の傷が化膿し苦しんでいたが、彼は強力な精神操作力を持っているため、錯乱状態でも周回軌道にいるエンタープライズをゆるがす力を発揮する。マッコイの治療でペルマンの傷は速やかに回復したが、彼はマッコイに惑星に残るよう命じる。

カークたち一行は救難信号を受け惑星スカロスに赴くが、住民は1人も発見できなかった。調査の最中、乗組員の1人が忽然と消えてしまい、一行は捜索空しく船へ引き上げる。ところがその直後から船の各機能に異常をきたし、生命維持装置に未知の機械が連結されているのが発見される。

新星に変わりかけているミナラの観測ステーションを撤収するため、カークとスポック、マッコイの3人はその第三惑星に赴く。ところがステーションには調査員の姿はなく、記録装置には彼らが怪光線と共に消え失せた場面が写っていた。そしてカークたちも同じ怪光線で惑星の地下に運ばれる。

宇宙艦隊司令部の極秘任務についたエンタープライズは、宇宙の彼方の恒星系におもむき、トロイアス星でペトリ大使を収容し、更にエラス星で王女エラン一行を収容した。この時初めて任務の内容が大使の口から明らかにされる。

惑星エルバ2に新薬を持って訪れたカークとスポックは、院長に化けたガースの人質となる。ガースは元宇宙艦隊の船長で、天才的な男だったが負傷し、その治療を受けた際、細胞再生の技術を学んで自由に変身する法も身につけたのだった。

病原菌に汚染された惑星アリアナスへ減菌の任務を受けて向かったエンタープライズは、基地から盗まれたシャトルクラフトを発見、収容する。中にはただ1人、顔が半白半黒の異星人が乗っていたが、セロン惑星のロカイとしか名乗らない。

同盟に参加するよう交渉中の惑星ギデオンは、代表としてカーク1人だけ受け入れると通告してくる。ところが、ギデオン側の示した座標に従って転送されたカークは行方不明になり、ギデオンの代表オディン大使は彼が惑星には来ていないと主張する。疑惑を覚えたスポックだったが……。

わずか数千年前に形成されながら大気圏を持つ不思議な惑星を発見したエンタープライズは、そこに調査班を派遣する。惑星に到着したカーク、マッコイ、カトーそれに地質学者ダマートの4人はひどい地震に見舞われるが、その衝撃が鎮まった時、エンタープライズは消え失せていた。エンタープライズは何かの力によって、約一千光年の彼方に飛ばされていたのだった。

エンタープライズに伝染病が発生し、乗組員が全員倒れるのは時間の問題となった。カークとスポック、それにマッコイはその病気の特効薬ライタリンのある最寄りの惑星に赴くが、無人と思われたその星には、フリントと名乗る男が住んでいた。しかもその住まいには、地球の歴史上貴重な書物や、美術骨董品のたぐいが飾られていた。

盗まれたクルーザー・オーロラ号の拿捕を命じられたエンタープライズは船を発見するが、オーロラ号は逃走しオーバーヒートで爆発する。乗っていた者はかろうじて収容したが、彼らは科学者セブリンに率いられ原始生活に帰る運動をしているグループだった。

ある惑星の植物が伝染病で絶滅に瀕し、エンタープライズはそれを防ぐジーナイトを運搬する任務を受ける。ジーナイトは惑星アーダナのみ産する物質で、カークとスポックはアーダナの民政官の許可を受けそれを取りに赴くが、約束の積荷はなく、2人はトログライトと呼ばれる鉱山労働者に襲われる。

無人惑星を観測中に突然、スクリーンにリンカーンの姿が現れ乗船許可を求める。疑惑を抱いたままカークは乗船に応じるが、乗り込んできたリンカーンは本物そっくりで、スポックと共に惑星に降りるよう要請されたカークは、それに応じる気持ちになり……。

新星に変わろうとしていた太陽を持つ有人惑星に住民が1人もいないことから、カーク、スポック、マッコイの3人は調査に出かける。ところがライブラリーに1人、エトスと名乗る男がいて、3人を住民と間違えて避難するようアドバイスする。

惑星ケイマスIIから遭難信号を受け取り、カークたちは救援に向かう。そこで遺跡の調査をしていた一行のうち、隊長ジャニス・レスターと医師コールマン以外は全員死んでいた。放射能を浴びて重体だというジャニスに付き添っていたカークは、他の者が座を外した隙に彼女からフェイザー攻撃を受け、不思議な装置にかけられてジャニスと人格を交換させられてしまう。