President Satoru Iwata confirmed the game at his GDC keynote, saying that the device's stereoscopic screen has made a 3D Mario game possible on a handheld.
"Since 1996, when Mario appeared in 3D in Super Mario 64, it's always been hard for players to judge how to jump and hit a block floating in a 3D space," he said according to Eurogamer.
"Game developers are now able to invent any world we imagine. This leads to a new Super Mario to debut on the 3DS."
The team responsible for Super Mario Galaxy will be developing the "brand new" adventure.
Also shown was a temporary logo for the game, which featured a tail appearing from the O in Mario, which Iwata said would be explained at a later date.
The title will be fully revealed at E3 in June.