Kiedy Nintendo 3DS zostało po raz pierwszy ujawnione, nowy Paper Mario został ogłoszony jako jeden z pierwszych tytułów. W tamtym czasie pierwszy wpis Paper Mario na handhelda, był znany po prostu jako "Paper Mario", a zwiastun był pokazywany na targach takich jak E3, ale nigdy nie został oficjalnie opublikowany.
Nintendo zamilkło na kilka lat, aż pojawiło się ponownie jako Paper Mario: Sticker Star i zostało uruchomione pod koniec 2012 roku. Został wtedy przyjęty z mieszanymi lub pozytywnymi recenzjami, ale teraz jest powszechnie uznawany za najsłabszą pozycję w całym podgatunku Mario RPG.
Fani byli zasmuceni, ponieważ, opierając się na nielicznych materiałach z offu, które były znane z E3 2010, ten pierwszy zwiastun wyglądał zupełnie inaczej niż ostateczna gra, będąc bliższy tradycyjnej walce turowej z The Thousand Year-Door niż rozwiązywaniu zagadek w ostatecznej wersji gry za pomocą naklejek.
A teraz, po raz pierwszy od ponad 14 lat, w sieci pojawił się zwiastun prototypu Paper Mario 3DS. Został on opublikowany na YouTube przez usar Marionova i nie wiadomo, w jaki sposób ten zwiastun trafił do sieci.
Ostatnie tytuły Paper Mario, takie jak The Origami King, zostały przyjęte bardziej przychylnie, kup Sticker Star pozostaje jedną z niewielu "szarych owiec" w serii Mario. W wywiadzie dla Iwata Asks ujawniono, że to Miyamoto poprosił Intelligent Systems o uproszczenie historii i użycie tylko istniejących postaci Mario oraz nadanie szerszego kontekstu temu, jak ten oryginalny prototyp - nigdy wcześniej nie widziany z takimi szczegółami - został zmieniony w Sticker Star.