The game is far more difficult than the original Super Mario Bros., due to a slightly modified game engine and more difficult level design. Unlike the original, Super Mario Bros. 2 does not have a two-player mode. Instead, the player chooses to play either as Mario or as Luigi in the single-player. Also unlike the original, Mario and Luigi differ in statistics. Luigi can jump higher and farther, but Mario is a more agile runner and has better traction (allowing him to stop moving more easily). The game's storyline, on the other hand, remains virtually unchanged. In many aspects overall, the game is very similar to its predecessor.

Super Mario Bros.: The Lost Levels includes various new obstacles and enemies to make it more difficult and diverse, although there are not very many new ones, making it extremely similar to the original game. The new obstacles and enemies found throughout the game are:

The Poison Mushrooms, which yield the same effect as being touched by an enemy.

Backward warp zones which warp the player to a previous level. For example, World 3-1 has a warp zone that warps the player back to World 1. Backward warp zones still count as warp zones, thus not allowing the player to access World 9 if they have taken one.

Strong green-colored jump trampolines which bounce Mario and Luigi much higher than normal red-colored jump pads.

Red Piranha Plants which come out of their pipes even if the player is standing next to them. They still do not come out if the player is standing on top of them.

Bloopers which float through the air.

Strong gusts of wind which blow intermittently, and often must be used in order to make long jumps, but which make controlling movement more difficult.

Bowser is seen twice, near the midpoint of the World 8-4 and World D-4. His appearance is a bit darker than the normal King of the Koopas. His appearance is the same in the All-Stars version.

A minor change in the ending, where she reads the player a poem. Princess Peach's theme has been remixed to use the Famicom Disk System's sound capability. These changes are only in the original FDS version, as well as the GBA version.

Certain Koopa Troopas will give Mario and Luigi an extra bounce when jumped on, usually to traverse a large gap or reach a high platform.

The game also features a total of five secret worlds with four levels each. World 9 (or "Fantasy World" as it is also known in the original release) can be accessed by completing the game without using any warp zones. The other four secret worlds are labeled A through D. To access these worlds, the player needs to finish the game eight times, then hold the A button and press Start on the controller at the title screen. (In the Super Mario All-Stars version, World A simply appears after World 9. If the player does not qualify for World 9, it appears after World 8.)