As with anything, it must be born from an idea. A bunch of creative ideas (brainstorming) either from a group or by getting stimulated by different things such as movies or games, and you will be ready to write a Game Design Document which gives you the advantage of having a complete overview of the project and hopefully give an order to an otherwise messy and chaotic bunch of random ideas.
Multiple mechanics often work with a story, but let's assume the protagonist is a skater... A turn based combat system would not work, and you are too understaffed to make an open world game in Jet Set Radio style, so you'd probably come up with a platformer-racing game instead.
Likewise, if the protagonist is a boxer and you want to give more focus on the story (A novel), you could just have a very simple minigame for boxing fights, and decide to drop any complex mechanic.
At that point you'd need to pick the engine that makes your life easier, and go from there.
Once you have a story and decided on a gameplay style and mechanics, you can test them (to balance and see if they are fun) by making the famous "Developer room", a level/scene where you drop that stuff for the sake of quickly testing everything.
If it works, go for it else back to the drawing board.