El sapo Wart ha encerrado a un pueblo de subcon, unas hadas pacíficas que habitan en el mundo de los sueños, y ahora Mario, Luigi, la princesa Peach y Toad deberán enfrentarse a Wart en el mundo de los sueños para rescatarlo. Los personajes jugables tienen la habilidad de agarrar hortalizas plantadas en el suelo para usarlas como armas arrojadizas. En lugar de aplastar a los enemigos al caerle encima, tu personaje simplemente se quedará arriba de él mientras el enemigo sigue moviéndose, pudiendo usarlo como plataforma móvil o aprovechar esa posición para agarralo y lanzarlo a otro enemigo.

Al empezar cada nivel podrás elegir cuatro personajes para controlar. Mario es el personaje más equilibrado, Luigi salta más alto y cae más lento, Toad corre y arraca las hortlizas más rápido y Peach puede flotar en el aire durante un instante, moviéndose en línea horizontal. Podrás saltar más alto si te agachas durante un instante para cargar el salto. Tu barra de salud tiene dos puntos al empezar cada nivel, pudiendo encontrar setas que aumentarán en un punto, pero solo durante ese nivel. En algunos lugares del nivel un corazón empezará a flotar hacia arriba y te restaurará un punto de salud si lo consigues. También encontrarás bloques POW, que podrás agarrar y acabará con todos los enemigos en pantalla al lanzarlo siempre que esteń en contacto con el suelo.

Hay 7 mundos con 3 niveles cada uno a excepción del último, que tiene 2. Cada mundo tiene una temática, pero hay algunas que se repiten. El objetivo de cada nivel sigue siendo llegar a la meta, pero ahora los niveles no tienen un diseño lineal y la meta no está en el extremo derecho del nivel. Habrá que ir hacia la derecha, la izquierda, arriba o abajo según nos demande el nivel. Mientras que para ir hacia la izquierda y la derecha la cámara nos acompañará, para ir hacia arriba y abajo habrá una transición cuando nos acerquemos hacia el extremo superior o inferior de la pantalla. Esto se debe a limitaciones de la NES, la consola en la que aparició inicialmente el juego, ya que no era capaz de hacer que la pantalla se moviera en diagonal. Te encontrarás puertas cerradas y deberás desviarte de tu camino para encontrar la llave. Cuando agarres la llave, que funciona como cualquier otro objeto que agarras en el juego, una máscara te perseguirá e irá flotando por la pantalla intentando embestirte mientras intentas llegar a la puerta con la llave. Al final de la mayoría de los niveles te esperará Birdo, a la que deberás vencer para abrir la salida del nivel. Birdo te lanzará huevos por la boca y deberás subirte a ellos mientras se mueven en el aire para agarrarlos y lanzárselos. Al final del último nivel de cada mundo habrá un jefe que deberás vencer devolviéndole sus propios proyectiles o usando como proyectil objetos del escenario.

Si este juego se siente tan diferente al primer Super Mario Bros. es porque es otro juego completamente distinto. El juego que originalmente se lanzó en Japón como Super Mario Bros. 2, que era idéntico a su precuela, fue considerado demasiado difícil por parte de Nintendo of America para su audiencia, así que cambiaron los personajes de un juego llamado Yume Kojo: Doki Doki Panic por los del universo Mario y vendieron este juego como la secuela de Super Mario Bros. Al final ciertos enemigos fueron absorbidos por el universo Mario y salieron en posteriores juegos, como Birdo o esos enemigos enmascarados llamados Shy Guys, que se volvieron un tipo de enemigo icónico de los juegos de Mario.

Este juego fue probado usando el núcleo FCEUmm de Retroarch y funciona perfectamente.