They started each game from the interactive experience and then fleshed out the details from there. Think running and jumping in Mario - they spent months getting the gravity and speed right, the button presses, all before the first thoughts to art, level design or story.
It was very iterative. They'd start with a concept and then tweak and tweak and tweak until it was as fun as they could get it.
Another good example is the development story of Super Mario Kart[1], which was supposed to be the sequel to F-Zero[2], but they invented/discovered new gameplay elements that fit better with the Mario brand and they took the game in that direction.
[0]https://en.wikipedia.org/wiki/Nintendo_Entertainment_Analysi... [1]https://en.wikipedia.org/wiki/Super_Mario_Kart [2]https://en.wikipedia.org/wiki/F-Zero_(video_game)