Da Nintendo 3DS først ble avslørt, ble et nytt Paper Mario annonsert som en av de første titlene. På den tiden var det første Paper Mario-innlegget på en håndholdt, det var ganske enkelt kjent som "Paper Mario", og en trailer ble vist på messer som E3, men aldri publisert offisielt.
Nintendo var stille i et par år, helt til det dukket opp igjen som Paper Mario: Sticker Star og ble lansert i slutten av 2012. Det ble mottatt med blandede til positive anmeldelser den gang, men er nå allment ansett som det svakeste bidraget i hele Mario RPG-subsjangeren.
Fans var lei seg fordi den første traileren, basert på det lille som var kjent fra E3-messen i 2010, så veldig annerledes ut enn det endelige spillet, og var nærmere den tradisjonelle turbaserte kampen fra The Thousand Year-Door enn det endelige spillets gåteløsning med klistremerker.
Og nå, for første gang på mer enn 14 år, har traileren til Paper Mario 3DS-prototypen dukket opp på nettet. Den er lagt ut på YouTube av usar Marionova, og det er ukjent hvordan denne traileren har nådd nettet.
Nyere Paper Mario-titler som The Origami King har fått en mer positiv mottakelse, men Sticker Star er fortsatt en av de få "grå sauene" i Mario-serien. Det ble avslørt i Iwata Asks-intervjuet at det var Miyamoto som ba Intelligent Systems om å forenkle historien og bare bruke eksisterende Mario-figurer, og gi mer kontekst til hvordan den opprinnelige prototypen - som aldri før har blitt sett med slike detaljer - ble endret til Sticker Star.