When Mario gets a star he will become invincible for a short time and you'll hear the Invincible BGM tune. During this time you are immune to all enemies, and the only thing that can kill you is falling off the screen.
The title comes from the Famicom 20th Anniversary Original Sound Tracks Vol.1 album.
Listeners have compared the song with the main riff and chord progression of What's the Buzz? by Andrew Lloyd Webber (from the Jesus Christ Superstar).
Super Mario Bros. (NES)
This song plays very rapidly, and sounds really crazy when you're running out of time. Both versions of the song loop.
Super Mario Bros. 2 (NES)
Koji Kondo remixed the Invincible music for Super Mario Bros. 2 with a nice percussion on the PCM channel.
The game's official soundtrack uses the title "無敵 (Muteki)" which means "Invincible," but doesn't use the BGM suffix.
The song is track 5 in the NSF file.
Dr. Mario (GB)
Syobon Action (W32)
The Syobon Action version is just recorded to MP3 song from the Super Mario Bros. (NES) with bad sound quality. The song is used on the level 3 inside the "trap level": you'll get onto it if fall to the nearest pit from the beginning - you'll jump into this level. The player will get a lot of money, but will be killed immediately while getting outside the trap. The character won't be invincible during the playback of this song.
The song file has the name "star4.mp3" in the game resources.