Well, for me its generally story, but that doesn't mean a map doesn't come first... For the most part a map is really required, at least a quick rough sketch...

We need to remember thats maps become out of date as soon as their made, so for every story a map will only be accurate for a tiny portion of it... So, if the map is rendered obselete because of story evolution (a city is taken over, a drought dries up a lake)... then that is to be expected... but if you change a place name, or the locations, or cultures, thats where you run into a problem... and thats where a rough sketch map comes in handy, since its lays out the basics before you start anything, it will highlight the guidelines to what your doing, and you know (if you decide to keep the rough sketch as law) that whats on the rough map won't change...