Nach dem erstellen eures Speichers, fängt die lange Geschichte von Starfox Adventures an. Ihr seht die Wölfin Krystal, die auf einem Cloudrunner fliegt. Ein seltsames Schiff erscheint vor euch und es greift euch an. Da ihr unendlich Leben habt, ist dies nicht sonderlich schwierig. Ihr beschießt zuerst die Geschütze, bis beide brennen. Danach den die Schiffsschraube. Die Gallone wendet und ihr müsst die Schiffsspitze attackieren. Ihr werdet nun aufs Schiff gelassen.

Dort wird euch die Steuerung erklärt. Am besten ist es, ihr erkundet nicht das Schiff, sondern geht sofort auf die andere Seite, wo ein Hängekäfig ist, in dem ein Baby-Cloudrunner gefangen ist. Dieser erklärt euch wieder einen Teil der Steuerung. Außerdem sagt er, ihr solltet im Schiffsbauch nach einem Schlüssel suchen. Ihr seht, welche Tür sich öffnet. Dort kommt ihr in das Innere des Schiffs. In der Mitte, auf einem Tisch liegt, gut sehbar, der gesuchte Schlüssel. Mit "A" nehmt ihr ihn auf. Geht zurück zum Käfig. Dort erscheint der grausame General Scales. Eine Videosequenz zeigt ein Gespräch zwischen Krystal und ihm. Das Ergebnis ist, dass Krystal über Bord geworfen wird. Der treue Cloudrunner rettet sie allerdings. Krystal fliegt zum Krazoa Palast weiter und wird dort abgesetzt.

Dort angekommen, sucht ihr an der Wand ein Schlüsselloch. Mit dem gefundenen Schlüssel öffnet ihr die geheime Kammer. Dort liegt ein Benzinfass. Sobald ihr diesen auf einen nahegelegenen Gegner werft, werden die Fässer auf der Plattform immer wieder nachproduziert. Sprengt euch den Weg nach unten. Ihr lernt die Eier kennen, die euch heilen. Seid ihr ein paar Meter nach unten gegangen, seht ihr eine rissige Wand. Ein Benzinfass von oben hilft euch, diese einzureissen. Im Gang, den ihr dann betretet, findet ihr einen verletzen Dinosaurier, an dessen rechten eines dieser Fässer und eine rissige Stelle in der Wand ist. Sprengt diese und gelangt in einen kurzen Abschnitt mit Feuerwerfern an beiden Wänden. Geht zurück zum Gang und lauft auf die andere Seite. Dort ist eine Fass-Plattform. Nehmt das Fass, der schon darauf steht und eilt zurück zu den Feuerwerfern. Wartet, bis diese eine kurze Pause von einer Sekunde machen, um durchzugehen. Am Ende dieses Abschnitts seht ihr wieder einen Riss in der Wand. Setzt das Benzinfass ein, um durchzukommen. Im nächsten Raum findet ihr einen Schalter, der die Wand mit dem Krazoa-Zeichen öffnet. Wollt ihr durch die neue Öffnung aber hindurchgehen, schließt diese sich wieder. Holt einfach ein Fass und stellt es auf diesen Schalter. Das Fass lässt die Wand offen. So könnt ihr durchgehen. In dem folgenden Raum liegt auf dem Boden ein verwunderter und deprimierter Earthwalker- Dinosaurier. Sprecht mit ihm und er öffnet das Tor zur Krazoa Prüfung. Stellt euch nun auf das Warpfeld und drückt "A".

Ihr erscheint in einem ähnlichen Raum. Klettert die Leiter hoch und geht zum roten Tor. Dies ist ein versiegeltes Tor. Dort seht ihr, wie viele Gegner in der Nähe erledigt werden müssen, um durchkommen zu dürfen. Dort ist eine Seele, die das Tor umfliegt. Das bedeutet, ihr sollt einen Gegner besiegen. Damit wäre das Flugmonster gemeint, was im Becken im Kreis fliegt. Nehmt das Benzinfass neben euch und werft es auf das Monster. Das Tor öffnet sich. Im nächsten großen Raum betätigt den großen Schalter und rennt zum Krazoa-Geist am anderen Ende. Ihr habt wenig Zeit. Deswegen, rennt ihr am besten durch die Feuerwerfer hindurch und rollt euch ab. Damit löscht ihr das Feuer an der Kleidung. Sprecht mit dem Geist und er erteilt euch eine Aufgabe. Der "Test der Observation" folgt darauf. Achtet, in welchen dieser Steine, der Geist sich versteckt. Folgt aufmerksam mit eurem Blick dem Stein. Sobald alle Steine zum Stillstand kommen, lauft zum richtigen. Dies wiederholt drei mal und der Geist dringt in euren Körper ein. Ihr verlasst diesen Ort und seid wieder beim verletzten Earthwalker.

In diesem Raum geht ihr zur Säule, die hoch schwebt, wenn ihr euch darauf befindet. Im engen Gang, seht ihr eine Statue eines metallenen Krazoa-Geistes. Stellt euch Davor und drückt "A". In der folgenden Sequenz wird Krystal den Geist abgeben und von einer unbekannten Mach gefangen genommen. In einem Eiskristall ganz oben am Tempel schwebt sie und ist in einem Trance-Zustand.

Eine Videosequenz stellt das Team "Starfox" vor. Es hat seit 15 Jahren keinen großen Auftrag mehr erhalten und ist seitdem ziemlich arm geworden und nicht mehr auf dem neuestem Stand der Technik, was Flugzeuge und Ausrüstung anbelangt. Da erhalten sie einen Anruf von General Pepper. Dieser berichtet von dem Planet Sauria, der auseinander fällt und womöglich das ganze Lylat-Universum zerstören könnte. Fox wird mit der Mission auf den Planeten geschickt, herauszufinden, was die Ursache des Zerfalls ist und den Planeten zu retten.

Bereits die Reise zum Planeten ist ein eine Aufgabe für euch: Ihr müsst auf der Strecke mindestens ein Goldring durchfliegen und darauf achten, nicht von den Gegnern erledigt zu werden. Wenn die Strecke zu Ende ist, kommt ihr auf den Planeten. Ihr landet in einer grünen und üppigen Landschaft. Hier ist kein Zeichen des herrschenden Kriegs und des Zerfalls zu sehen. Dieser Ort heißt "ThornTail Tal". Zu Deutsch: Stachelschwanz-Tal. Dieser heißt so, weil die Bewohner Stacheln auf dem Rücken haben. Dies sind allerdings friedliche Pflanzenfresser. Geht ihr direkt nach dem Landen am Fluss vorbei, findet ihr eine Stelle in der Wiese, in der ein Stab steckt. Es ist Krystals Waffe: Der magische Stab. Zieht ihn mit "A" aus dem Boden und ihr erlernt , mit ihm umzugehen. Das erlernte Wissen wendet ihr im kleinen Hof direkt daneben an, wo ihr vier Sharp-Claws antrefft. Dies sind feindliche Dinosaurier, die zur Armee von General Scales gehört. Besiegt diese und über der Tür des Gebäudes, aus dem die Gegner gekommen sind, erscheint ein rotes Feld, mit einer sonne darauf. Außerdem öffnet sich hinter dem riesigen Brunnen auf der anderen Seite des Flusses eine kleine Höhle. Geht dorthin. Da es viel auf dem Planeten zu finden gibt, lasst immer den Info-Scanner an. Dort könnt ihr immer Lesen, worum es sich bei einem Objekt handelt. In der Höhle angekommen, hievt mit "A" den Stein hoch. Denn darunter befindet sich ein Loch, aus dem es grünlich schimmert. Der Stab wird ebenfalls Grün und euer Player vibriert. Springt in dieses Loch hinein und ihr befindet euch in einer unterirdischen Grotte. Springt ihr in die Mitte des Kreises, befindet ihr euch auf einer Plattform. Drückt "A", um eure erste Attacke mit dem Stab zu erlernen: Das "Inferis". Hinter euch schließt sich das Tor zum Ausgang dieser Grotte. Eine rote sonne erscheint, wie vorher auf dem Tor. Schießt darauf, damit die Sonne grün wird und ihr passieren dürft. Geht raus zur anderen Sonne, um diese auch grün zu färben. Betretet das Gebäude.

Es Liegt ein verwundeter Earthwalker auf dem Boden. Doch diesmal mit Rosa Steinen geschmückt und weiblich aussehend. Es ist die Earthwalker Königin die ihren Sohn, den Prinzen vermisst, der von den Sharp-Claws entführt wurde. Sie bittet euch, ihn auf der Eisspitze zu suchen. Wie ihr dort hinkommt, erklärt sie euch nicht, allerdings lässt sie den Eingang zu einem riesigem Steingolem enthüllen. Ihr müsst euch nun mit den verschiedenen Dingen auf Sauria auseinander setzen. Geht zu einem Steinkreis und hievt alle Steine hoch, um Peser, grüne Käfer zu erhalten. Das ist die Währung des Planeten. Zerschießt die rundliche Pflanze, um Bombensporen zu erhalten. Das sind Samen dieser Pflanze, die ihr an weichen und erdigen Stellen einpflanzen könnt, um sie zum sprengen von Wänden zu benutzen. Geht zu den kleinen Palmen und zerschlagt sie, um Kristalle aufsammeln zu können. Euer Stabmagiemeter wird dadurch aufgefüllt. Dieser zeigt, wie viel Energie ihr noch für Attacken mit dem Stab habt. Sprengt ihr den Eingang zum Golem, redet mit diesem. Er ist verbittert, weil er einsam ist und weil ihm seit 1000 Jahren niemand mehr etwas geschenkt hat. Unter der Plattform des Golems findet ihr einen Eingang zu einer orientalisch geschmückten Höhle. Dies ist der Basar. Er wird von einer Schlange geführt, was die Ehrlichkeit dieser gut beschreibt. Ihr könnt nützliche Dinge dort mit den Pesern kaufen. Da ihr erst 10 sammeln könnt, ist es nur möglich Karten zu kaufen, die ihr nicht braucht, oder eine Steinpraline. Kauft diese und geht zum Golem. Wählt die Praline aus dem Inventar aus und schenkt sie ihm. Er freut sich über dieses kleine, aber besondere Geschenk. Er fragt euch, was ihr denn wollt. Fox sagt, er wolle zur Eisspitze. Euch wird erklärt, wozu der Golem nützlich ist: Er kann euch zur Eisspitze, zum geheimen Labyrinth oder zum Krazoa-Palast bringen. Wählt die Eisspitze und er teleportiert euch dorthin.

Ihr seid nun auf einem Warpfeld, wie ihr es aus dem Krazoa-Tempel mit Krystal kennt. Verlasst die Höhle, in der ihr euch befindet und ihr seht, wie ein Flugzeug landet und zwei dieser Sharp-Claws raus lässt. Außerdem kommt ein kleiner Earthwalker zum Vorschein. Das ist Prinz Tricky, der vermisste Sohn der Königin . Die zwei Entführer nehmen ihn mit in eine kleine Höhle und verschließen diese mit einem Tor. Nehmt ein Benzinfass mit Zeitzünder und werft es auf eine nahe gelegene Wand aus Kisten. Geht hindurch und tötet dort die Wachen. Eine rote Sonne erscheint über dem Höhleneingang. Schießt auf diese und ihr könnt eintreten. In der Nachfolgenden Sequenz seht ihr, wie Fox versucht Tricky erfolglos freizukämpfen. Da die Sharp-Claws abgelenkt sind, rennt Tricky schnell weg. Die Entführer nehmen die Verfolgung mit Flugschlitten aus der Höhle auf. Für Fox bleibt auch ein Schlitten und es folgt ein Rennen. Dort müsst ihr als erster im Ziel ankommen. Mit einem Trick gewinnt ihr ganz sicher: Fahrt am Anfang sehr schnell und überholt mit einer Sprungchance beide Gegner. Sobald der erste enge Tunnel kommt, bremst ab und stellt euch quer hin, damit die Verfolger nicht an euch vorbeikommen, sondern wegen der Kollision erledigt werden. Nun gibt es keine Gegner mehr und ihr könnt unbesorgt ins Ziel fahren.