I find that inspiration strikes me in the form of "Moments"- kind of like snapshots of what a game should be and the reactions it should elicit from the player having the experience. Like Shadow of the Colossus' moment would be delivering the killing blow to a giant beast while hanging on for dear life- the feeling of victory against insurmountable odds, coupled with a constant acute fear of being thrown off and having to start over. The whole game is built off of those moments. I'm sure that the story was written to facilitate getting to have those experiences.

Sometimes the story is as much a part of those fundamental moments as the gameplay itself. for instance, none of Chrono Trigger's "Moments" are inside of a battle sequence. instead, they usually directly follow one. The feeling of wiping out an enemy with Luminare is totally trumped by that time when Chrono sacrifices himself in the battle with Lavos, or the face-off between Frog and Magus, or when Robo gets himself trashed by his own Robot friends. Those are story driven Moments- the gameplay serves to break up the plot, and uses the next chunk of plot as a reward for beating a boss or making it through a dungeon.

I've heard that music bands often have hundreds of song progressions without lyrics, and similarly hundreds of lyrics without song progressions. The lyricist might write words for a particular music track that he has in mind, or he might write something he feels is really compelling and spend time working out an appropriate track to put the words to.

Sometimes production works forward, sometimes it works backwards.

I personally find everyone's opinion as very instructive. In fact, I must say that all the members has got its very good deal of reason and that if there is an absolute answer to the complexity of having to choose between story or mechanics, no doubt it will be a mid term between all these contributions.
If I had to be more explicit, both options complement each other, as the mechanics can grow up from a slightly more mature story and vice versa.

I can speak from the perspective of writing recent (ie. post commercial era) story-driven sidescroller platformer / shooter games on the Commodore64. These are for the most part solo efforts.

It's not necessary to have fully detailed story first (ie. down to each line of dialogue), and code can be started as soon as you know roughly what kind of gameplay mechanics there are going to be. However I would advocate having the basic progression of the story down before the game world design and artwork production starts, to make sure the locations flow logically and no artwork is wasted. Personally the world artwork production represents the most grueling part for me so it has a heightened importance to get right; may not represent an universal truth.

Certainly, there is going to be (or should be) back-and-forth interplay of the story and mechanics during development; otherwise you may miss many wonderful creative opportunities.

I was eating lunch with a friend today and they mentioned that most game companies create a game first and do the story last. I, however, am a strong advocate for creation of story first. Preferably before even one line of code is written. So a question for those who have done it. Does your company write the story first when tossing around an idea for a new game (even just a rough draft) or do they do the story last, and why?

Ah, the question of top-down design...

By "default", story comes last primarily because the focus is set on gameplay, and a story is created to fit that.

That being said, there are a number of reasons why you might want to have story first (top-down design).

Reasons I can think from the top of my head:

- In Magic The Gathering, the development team chose to do something bold for one of their sets (Innistrad I believe?) where they simply decided to start with the story and design mechanics based on that.

- Some games are deliberately more interactive stories than games, and require top-down design to work. A lot of modern AAAs, for example, are inherently top-down, though certainly not all. Assassin's Creed, for example, hinges a lot more on story than Batman: Arkham City (I need to update my references, sorry!)

- Brand management: when a game gets developed for pre-existing media (a tv series for example) you already have very rich content to draw from (story-wise). It's generally easier and more desirable to draw from this content.

- "Reskin": Using pre-existing game mechanics and reskinning can be a boring process, but to make a more "fun" game, it's best to start with the game's story and re-implement the core mechanics of the targeted proven gameplay (thus reducing "fun factor" risks).

All in all, story or game first depends entirely on the mindset behind the project being undertaken.

'story' can have level of detail.

Story basics are needed (need to preexist) to define the players part in the games 'story' (what interactions possible, what and how things are presented, etc...) , so have to be decided early - for the game engine/whatever mechanisms to be built with the required features

Later game interface mechanisms may have to be further developed/added to help fill-in presentation of the desired 'story'

Much later, various story 'filler' employing the game mechanisms to finish the extent and detail of what story is being told (much which doesnt actually directly affect the game interactions other than presenting context and motives and explanations.)