En 1998, Hideki Konno et Takashi Tezuka, à qui est confié le projet, décident de changer la donne : peut-être libérés de l'oeil inquisiteur de Shigeru Miyamoto, célèbre créateur de Mario, les deux hommes décident de se concentrer sur le personnage secondaire qu'est Yoshi et de se séparer du héros à moustache. Leur projet se nomme Yoshi's Story et, pour la première fois dans l'histoire de Nintendo, le dinosaure vert prend vie dans un jeu de plate-forme qui lui est entièrement consacré.

L'histoire débute sur l'île légendaire des Yoshis, dont l'existence est régie par l'arbre magique du bonheur et de la joie, le Super Happy Tree. Transmettant ses bonnes ondes à l'ensemble de l'île, il assure aux Yoshis une existence paisible à l'abri des ennuis. Malheureusement, la jalousie d'un seul être va venir briser ce fragile écosystème : Baby Bowser, envieux de ce bonheur, jette un sort à l'île des Yoshis et la transforme en livre. Dans son entreprise de destruction, il va même jusqu'à voler aux Yoshis leur raison de vivre et s'empare de l'arbre magique, générant une atmosphère chaotique et instable sur l'île. Mais il existe un endroit reculé où six oeufs demeurent. Protégés du sort maléfique de leur bourreau, ils éclosent à l'abri du malheur et les bébés Yoshis décident, d'un commun accord, de partir à l'aventure pour rendre à leurs amis le bonheur qu'ils méritent.

Au premier coup d'oeil, l'histoire s'inscrit parfaitement dans l'univers développé par Nintendo au fil des ans. Résolument manichéenne, d'aucuns la qualifieraient même de profondément niaise si elle ne s'assumait pas de bout en bout. La grande force de Yoshi's Story est en effet de se poser d'emblée comme le parfait miroir du pays des Yoshis, qui ne sont finalement rien d'autre que des enfants. Dès l'allumage de la console, un "Nintendo" scandé en langage dinosaure installe aussitôt l'esprit qui sera observé tout au long du jeu, rapidement secondé par l'écran titre et ses chants Yoshis aux allures de berceuse. Le fait de désigner Baby Bowser comme méchant n'est pas anodin, et le sort qu'il lance à l'île inscrit définitivement ce jeu dans la catégorie des contes pour enfants. En effet, toute l'histoire est contée au joueur au travers d'un livre d'images, la carte du monde défilant au gré des pages que l'on tourne. Chaque région apparaît sous la forme d'un pliage vivement coloré qui nous renvoie à notre plus tendre enfance. L'analogie avec un livre est poussée jusque dans les niveaux eux-mêmes, puisque chaque section laisse place à la suivante grâce à un effet visuel qui suggère qu'une page se tourne.

Appartenant à la première génération de jeux supportant le Rumble Pak, Yoshi's Story se présente comme un jeu de plate-forme 2D au sein duquel sont intégrées des reproductions 2D de modèles 3D, à l'instar du travail déjà réalisé par Rareware sur Donkey Kong Country (Super Nintendo). Autant dire que visuellement, le jeu décoiffe. Tout au long de l'aventure, les développeurs se sont amusés avec différentes textures qui confèrent au titre un visuel unique, formant les nuages avec des pelotes de laine, le ciel avec des morceaux de jeans ou les rochers avec des revêtements en cuir. Chaque élément est savamment réfléchi, et il est improbable que l'on croise un arbre qui ne soit pas brillant comme un morceau de plastique, ou un château qui soit conçu autrement que dans un pliage de papier ou une sculpture de pâte à modeler.

Malgré ces quelques éléments 3D et certains passages trompeurs, le jeu est bel et bien en 2D et repose sur un gameplay adapté. Yoshi peut nager, sauter, planer un bref instant en maintenant la touche de saut, lancer des oeufs, faire des attaques rodéo et finalement tirer la langue pour avaler fruits et ennemis. En somme, il peut faire tout ce qu'il avait préalablement appris dans Yoshi's Island, à ceci près qu'il peut désormais renifler pour tenter de trouver des fruits cachés dans les arbres ou dans le sol. En revanche, même si les deux jeux partagent quasiment les mêmes mécanismes, il est important de noter que ces derniers ne sont pas mis au service des mêmes défis. En effet, là où Yoshi's Island pouvait se révéler ardu, Yoshi's Story persiste dans son esprit enfantin et peut sans mal se boucler en une toute petite heure dès la première partie. Répartis en six mondes - contre huit selon la norme Nintendo -, les niveaux sont au nombre de vingt-quatre seulement. De plus, si tous possèdent fatalement un point de départ, aucun d'entre eux ne possède de ligne d'arrivée ! Le joueur est ainsi condamné à errer dans chaque niveau jusqu'à ce qu'il remplisse le tour de l'écran grâce aux fruits gobés. Une fois que trente ont été mangés - une formalité -, le degré de bonheur est jugé suffisamment élevé et le niveau s'achève. Le joueur accède ainsi non pas au prochain niveau... mais au prochain monde !

Dans chaque niveau se trouvent également trois Coeurs Joyeux, plus ou moins dissimulés. Si le joueur n'en découvre aucun, un seul niveau sera accessible au prochain monde, réduisant fortement son choix. Si le joueur en découvre un, deux niveaux seront disponibles, et ainsi de suite jusqu'à un choix entre quatre. Néanmoins, sachant qu'il suffit de boucler un niveau pour accéder au monde suivant, on comprendra très vite que six niveaux suffisent pour parvenir jusqu'au château de Baby Bowser et assister à la fin du jeu. Les plus combatifs chercheront à récupérer tous les items pour accumuler un maximum de bonheur et tenteront de se nourrir qu'avec le fruit préféré de leur dinosaure - qui varie selon la couleur du Yoshi sélectionné parmi les six disponibles au début -, mais ceci ne parviendra pas à occulter le fait que le jeu reste d'une trop grande simplicité.

En dépit de l'excellence visuelle et sonore du titre, frais et charmant, le joueur moyen regrettera donc amèrement l'absence d'un réel challenge. Les comptes à rebours qui viennent habituellement rappeler le joueur à son devoir sont absents, au même titre que les ennemis qui se font très discrets. Si l'on excepte la jungle, où le joueur devra rester vigilant pour ne pas tomber dans l'estomac d'un poisson, les embûches sont tellement peu nombreuses qu'il n'est pas rare de se promener sans l'ombre d'un souci. Une caractéristique qui prive Yoshi's Story d'un plus grand dynamisme, et qui le destine encore davantage aux plus petits.