V papírové verzi Houbového království každý rok v městečku Decalburg přistane kometa Sticker Comet složená z kouzelných samolepek Royal Stickers, které dokáží splnit jedno přání. Komety se ovšem při každoročním festivalu pokusí zmocnit zlotřilý Bowser, jehož přání ji roztříští na samolepky, které se rozutečou po celém království. Ke katastrofě se připlete i instalatér Mario, který nevědomky vzbudí zlost samolepkové víly Kersti, jenž ho mylně pokládá za pachatele. Mario se tak společně s Kersti vydává na pouť celým královstvím za samolepkami a porážkou Bowsera...

Sticker Star je čtvrtou hrou ze série Paper Mario a jedná se o z boku viděnou akční adventuru s prvky RPG, v níž hráč v roli Maria a jeho společnice Kersti prozkoumává Houbové království s cílem najít všechny Royal Stickers. Hlavní mechanikou hry je tentokrát sbírání nálepek, z nichž Mario získává schopnosti nutné pro postup hrou, a to jak co se týče soubojů, tak interakcí s prostředím. Samolepky lze v režimu zvaném "Paperization" libovolně lepit po herním světě a řešit s jejich pomocí hádanky –⁠ například samolepka větráku zvedne vítr, který může odfouknout různé překážky. Samolepky své využití v podobě útoků najdou i v tahových soubojích, podobným prvním dvěma hrám ze série (Paper Mario a The Thousand-Year Door). Za vyhrané souboje však Mario tentokrát nedostává zkušenostní body a své statistiky může zvýšit pouze sbíráním HP-Up srdcí.

Série pokračovala dílem Color Splash pro konzoli Nintendo Wii U.