L'Invincibility BGM accompagne Mario lorsqu'il attrape une Super Star et devient temporairement invincible, capable de détruire tous les ennemis au simple contact. Le thème joue également dans les Coin Heaven, ces zones bonus accessibles via des haricots magiques. Écrit en do majeur avec une signature rythmique en 2/2 à 150 BPM, le morceau suit une progression cyclique alternant entre l'accord de ré mineur septième et do majeur septième. Comme le Ground Theme, le canal de bruit joue un rythme swing, contrairement aux arrangements ultérieurs qui utilisent des croches droites.

La composition de Koji Kondo crée une sensation d'euphorie et de puissance parfaitement adaptée à l'état d'invincibilité du joueur. La mélodie principale utilise la septième et la fondamentale des accords, tandis que la ligne de basse utilise la fondamentale et la quinte. Cette structure harmonique simple mais efficace génère un sentiment de joie et de triomphe qui accompagne Mario dans sa course destructrice à travers les ennemis. Le thème est devenu si iconique qu'il est immédiatement reconnaissable et associé au concept même d'invincibilité dans les jeux vidéo.

Ce thème est devenu l'un des plus récurrents de toute la franchise Mario, réutilisé dans sa version originale NES dans de nombreux jeux au fil des décennies. Dans la série Super Smash Bros., à partir de Brawl (2008), c'est la version originale qui joue lorsqu'un combattant attrape une Super Star. Mario Hoops 3-on-3 utilise également l'original pendant l'effet de la Super Star. Paper Mario: The Origami King permet d'entendre la version NES en équipant l'accessoire Retro Soundbox. Cette longévité témoigne de l'impact culturel de cette composition de six secondes en boucle.