À l'instar des autres jeux de la série, Mega Man V comporte huit boss à éliminer avant de pouvoir accéder aux niveaux plus avancés. Seulement, alors que ses prédécesseurs sur Game Boy se contentaient principalement de réutiliser des robots de la série classique sur NES, ce cinquième volet présente des boss complètement inédits, les Stardroïdes (Space Rulers au Japon) : Neptune, Mercury, Venus, Mars, Pluto, Uranus, Jupiter et Saturn.

Une fois les quatre premiers Stardroïdes éliminés, le joueur devra affronter Dark Moon, entité bionique en tout point similaire au Yellow Devil et, après être venu à bout des quatre autres, sera confronté à Terra, avant de s'envoler vers la forteresse spatiale du professeur Wily.

C'est d'ailleurs le seul jeu de l'univers classique de la série Mega Man dans lequel Wily n'est pas le boss de la fin. En fait, une fois la machine du professeur détruite, ce dernier activera, en dernier recours, le puissant robot Sunstar (Sungod au Japon). Ce concept sera repris dans Mega Man X8.

Comme dans Mega Man IV, si le joueur est battu à plusieurs reprises, mais choisit de continuer, Mega Man sera éventuellement téléporté au laboratoire du professeur Light pour y recevoir une amélioration extrêmement puissante de son Mega-Arm. En revanche, ce canon amélioré ne sera pas enregistré par un mot de passe et sera perdu si le joueur arrête le jeu.

En ce qui concerne le Mega-Arm, cette arme est très similaire au Rocket Buster de Mega Man 7 sur Super Nintendo. En outre, le joueur est encouragé à revisiter les niveaux pour y récupérer certains objets (comme des joyaux qui réduisent la consommation d'énergie pour les armes), un peu à la manière de Mega Man X et Mega Man 7.

Après avoir battu tous les Stardroïdes, Mega Man se retrouve confronté à Terra. Après l'avoir battu et obtenu le Spark Chaser, une étoile se faire découvrir par Mega Man, une étoile-forteresse comportant un crâne avec un "W" inscrit dessus. Mega Man devine alors qu'elle appartient au Professeur Wily. Mega Man part alors rattraper l'étoile-forteresse avec Rush.

Dans ce stage, nous sommes confrontés à une phase de shoot'em up. Rush doit tirer sur les vaisseaux ennemis et éviter les astéroïdes. Puis il faut détruire le canon laser de Wily, tout en évitant les balles d'en bas et en détruisant les missiles d'en haut.

Après avoir détruit le canon laser de l'étoile-forteresse, Mega Man s'infiltre dans cette dernière par le trou causé par les dommages de Rush. Dans ce stage, Mega Man doit affronter les Mega Man Killers une fois de plus. Mais cette fois-ci, Mega Man ne peut pas copier leurs armes. Comme dans Mega Man IV, nous devons affronter les huit robots déjà combattus. Après cela, nous devons combattre deux mains robotisées, une main gauche et une main droite. Finalement, nous sommes confrontés à la machine du Professeur Wily, comme dans les précédents opus.

On apprend au cours de l'histoire que Wily a découvert un robot très ancien, Sunstar, et s'en est servi comme modèle pour concevoir les Stardroïdes. Mais ses créations, bien que nettement plus puissantes que n'importe quel robot ordinaire, sont très vite détruites par Mega Man et Wily décide, en dernier recours, d'activer Sunstar.

Le nom de chaque Stardroïde correspond à une planète du système solaire. Il y a neuf robots à combattre tandis que dans les autres jeux de la série, il y en avait 8 à combattre.