Игра представляла заметно изменённый геймплей, менявший (и делавший более разнообразным) весь процесс прохождения игры и требовавший от игрока вырабатывания новой тактики поведения. Основное изменение коснулось схемы взаимодействия с противниками: принятая в предыдущих играх серии модель, в которой Марио мог убить врага, прыгнув на него сверху (если только это не был дикобраз Спини или кто-либо другой, защищенный шипами) была устранена. Вместо этого была добавлена возможность бросать в противника различные предметы, распределённые по игровым уровням (чаще всего выдернутые из земли овощи, а также других противников). Предмет можно взять, предварительно прыгнув ему на голову. Таким образом в Super Mario Bros. 2 противника можно убить только с помощью постороннего предмета, другого противника, либо взяв бонус — «звезду», дающую неуязвимость.

В игре был введён уровень жизни, измеряемый количеством красных шестиугольников в левом верхнем углу экрана. В предыдущих играх величины «здоровья» не было, при контакте с противником Марио моментально терял жизнь, а если в этот момент он находился в «продвинутом» состоянии, то возвращался в предыдущее (Fiery Mario и Super Mario становились обычным Mario). Таким образом в Super Mario Bros. 2 игрок мог несколько раз столкнуться с противником, прежде чем потерять одну жизнь.

Также игроку была предоставлена возможность выбора одного из четырёх игровых персонажей: Марио, Луиджи, Пич и Тоад. Раньше игрок мог выбирать только между Марио и Луиджи (и лишь в режиме двух игроков), при этом различие между персонажами заключалось в том, что Луиджи прыгал дальше Марио и сильнее «пробуксовывал». В то же время все четыре персонажа Super Mario Bros. 2 обладают уникальными для каждого из них способностями, определяющими стиль прохождения игры.

Помимо этого в игру была добавлена мини-игра, работающая по принципу однорукого бандита, в которой игрок может заработать бонусы, облегчающие прохождение.