It has been about 30 years since Mario was conceived in the mind of Nintendo employees. Thousands of games have come and gone, but Mario is still here, selling games by the literal boatload.

What is it that as given Mario such lasting appeal and overall recognition? What does it take for a franchise to remain relevant in 4 different decades? Why, in so many years, has not one VG character (outside of Nintendo) come anywhere close to this character's popularity?

Maybe it is:

• The music - Often times even the most mediocre of games live on through their musical compositions. In the Mario universe, even a single sound effect can be acknowledged as something from a Mario game. Its classic melodies have withstood the test of time, and still permeate today.
• The characters design- Mario is a weird character. He is round, and has a plump pinchable face, but he has a mustache...He is a grown man, but still childish in a way. He has a dangerous dynamic that somehow appeals to every type of person, as opposed to Sonic the Hedgehog, whose edge fends off certain demographics.
• The gameplay- who knew running and jumping could be expanded into such an amazing and engaging experience. The simple objective to move forward is something that has captivated every type of person who has played the platformers. With a game associated, Mario has been able to branch off into other genres with a dedicated fanbase trailing along for the next ride.
• The advertising- a game isn’t a big deal unless it has a cereal based on it, and Mario is that game. The stickers, hats, Halloween costumes, SM64 cameras, pins, billboards, corny film, lunchboxes and senseless commercials with a global Mario face has made people aware of Mario, and the fact that within pop culture, he has found his place.

So what do you think has made Mario the megastar?

The same reason zelda, final fantasy, dragon quest & other 20 year old franchises are still here

FANTASTIC & TOP quality with each main entry.....there was no reason for them to ever become irrelevant

gameplay is winning by a landslide even with the anchor called "story" attached to it

Gameplay and quality.

Already been said... but fantastic game design. Mario puts the 'k' in kwality.

Because Mario games have a unique and special feeling to them.
I mean, trade anything Mario for any relatively unknown franchise and the result would still be a good game, but with lower scores, lower sales, more critics etc.
The same goes for other game franchises like FF, Halo or almost any hit on the entertainment industry. You don't need to be a philosopher to perceive that.

All of the poll choices play a part, not just one

Every important industry needs to have history, and something that is timeless.

I think Tetris proved that, and Mario proves that continuously. At this point what really makes Mario popular is the core element of fun, and the fact that 2D Mario players... the true home console-based Mario audience was starved for 18 years...

But also there's a element of history which should be off limits either way, but is regardless very important to people. Videogaming was brought back from nothing and Mario is largely associated with that, along with having helped create a brand new industry in Japan, and recreate it again by converting new players on the DS.

It also has to do with the talents of the designers who first made it, including Miyamoto. They continued to provide their talents to the series, and it continued being quality software which is usually enough nowadays.

Gameplay. It's a timeless classic.

And since you mention "Story", there's something appealing about "SAVE THE PRINCESS!"