I have been writing a story for many years now and it has turned into three books, non published. I started with the story and only later added a map. The map began as a sketch and I filled in stuff along the way. There have been three versions and the latest is posted over here, if you are curious: http://www.cartographersguild.com/showthread.php?t=2977

My world is pretty small though, with only a few nations and cities, so I had no problems starting the story. I can imagine if you are writing a story on multiple continents, dozens of nations, you might want to start with at least a sketch first

Oh, and like Steel General I have written several short stories and I didn't need a map for them.