Toen de Nintendo 3DS voor het eerst werd onthuld, werd een nieuwe Paper Mario aangekondigd als een van de eerste titels. Destijds was het de eerste Paper Mario-inzending op een handheld, het stond gewoon bekend als "Paper Mario", en een trailer werd getoond op beurzen zoals E3, maar nooit officieel gepubliceerd.
Nintendo zweeg een paar jaar, totdat het weer opdook als Paper Mario: Sticker Star en eind 2012 werd gelanceerd. Het werd toen met gemengde tot positieve recensies ontvangen, maar wordt nu algemeen beschouwd als de zwakste inzending in het hele Mario RPG-subgenre.
Fans waren bedroefd omdat, op basis van de weinige off-screen beelden die bekend waren van E3 2010, die eerste trailer er echt anders uitzag dan de uiteindelijke game, omdat hij dichter bij de traditionele turn-based gevechten uit The Thousand Year-Door stond dan bij het oplossen van puzzels in de uiteindelijke game met stickers.
En nu, voor het eerst in meer dan 14 jaar, is de trailer voor dat Paper Mario 3DS-prototype online opgedoken. Het is op YouTube geplaatst door usar Marionova, en het is niet bekend hoe deze trailer op internet is terechtgekomen.
Recente Paper Mario-titels zoals The Origami King zijn gunstiger ontvangen, koop Sticker Star blijft een van de weinige "grijze schapen" binnen de Mario-franchise. In het Iwata vraagt-interview werd onthuld dat het Miyamoto was die Intelligent Systems vroeg om het verhaal te vereenvoudigen en alleen bestaande Mario-personages te gebruiken, en meer context te geven aan hoe dat originele prototype - nog nooit eerder met zoveel detail gezien - werd veranderd in Sticker Star.
