Before that he was just Jumpman rescuing a damsel from a kong that couldn't be called king for intellectual property reasons, and the genesis of a gorilla being involved at all was nintendo's loss of the popeye license.

He didn't become Mario until there was a two player sewer themed game requiring names for the protagonist plumber brothers.