Het zonnetje schijnt en Mario is onderweg naar het kasteel van prinses Peach voor het feest dat gegeven wordt ter ere van de komeet die eens in de honderd jaar de planeet passeert. Als Mario bijna bij het kasteel is, wordt de idyllische sfeer ruw verstoord door Bowser die aanvalt met zijn luchtschepen. De inwoners van Mushroom Kingdom worden gevangen in ijs en Bowser stuurt een ufo naar het kasteel van Peach, die het kasteel mee de ruimte in neemt. Mario weet op het laatste moment nog op het kasteel te geraken, maar wordt kort daarna door de magische Koopa Namek de ruimte in geschoten.

Even later ontwaakt Mario op een kleine planetoïde en maakt hij kennis met Tyke, een Luma, en begint de tutorial waar een drietal konijnen gevangen moet worden. Als dit is gebeurd, maken we kennis met prinses Rosalina op haar kometenobservatorium annex ruimteschip en zij vertelt ons wat er aan de hand is: Bowser heeft alle power stars en de zeven grand stars gestolen van Rosalina's schip, dat nu hulpeloos door de ruimte zweeft. Mario moet deze sterren verzamelen om het schip weer van energie te voorzien en daarna naar het centrum van het universum te reizen om Peach uit Bowsers klauwen te redden, en daarmee het universum.

De typische Mario-sfeer is gezet en als speler mag je aan de slag. Vanuit Rosalina's schip kan je observatoria betreden om naar verschillende sterrenstelsels te worden gelanceerd en daar sterren te behalen. Naarmate de speler meer sterren behaalt, worden nieuwe observatoria en stelsels toegankelijk. Naast het verzamelen van sterren moeten er ook munten en 'star bits' verzameld worden. De munten vullen de ronde levensmeter van Mario aan, en de star bits kunnen gebruikt worden om vijanden te verlammen en hongerige Luma te voeden, die je daarna verder kunnen helpen op je avontuur.
Gameplay
Omdat het spel zich afspeelt in de ruimte en op planetoïden, is er een heel scala aan nieuwe gameplaymogelijkheden. Een rondje om een kleine planeet is snel gelopen en Mario kan van de ene naar de andere nabijgelegen planetoïde overspringen. Ook is het mogelijk om de zwaartekracht te tarten door op bepaalde muren of plafonds te lopen. De spelomgevingen zijn voorzien van allerlei puzzels, hindernissen en andere uitdagingen. Verder kan Mario speciale paddenstoelen gebruiken die zijn outfit en mogelijkheden veranderen, zoals een bijenpak waarmee Mario naar de reusachtige bijenkoningin moet vliegen en star bits uit haar vacht moet halen.

De moves van de Italiaanse loodgieter zijn ook uitgebreid ten opzichte van de voorgaande delen. Met name de Wii remote speelt hier een grote rol bij: als de speler deze heen en weer schudt doet Mario een star spin waarmee vijanden verlamd kunnen worden en waar bepaalde voorwerpen mee geactiveerd kunnen worden. Verder heeft de besturing veel weg van Super Mario 64 en Sunshine: rondlopen gebeurt met de analoge stick op de nunchuck, om te springen druk je op A en op B drukken zorgt ervoor dat er een star bit wordt afgeschoten, waarbij je mikt op het scherm. Ook kan de speler de afstandsbediening op het scherm richten om zo star bits te verzamelen.