It's kind of complicated for me.
I'd say "character first" but on the other hand it's really hard for me to come up with characters that are not tied in my mind to any story, just existing in a vacuum. Also many of the characters I use the most are recycled versions of my much older characters, created for completely different stories, so that further complicates it.
It's really kind of a chicken vs. egg situation.
Usually it tends to go like this, for main characters at least (but even so, there are exceptions):
very vague general story idea --> character concept and basic design --> a slightly more detailed story concept --> more detailed concept for the character, fleshing out the design --> actually developing the story, tweaking the character alongside it.
It's less complex for supporting characters: these are usually created later, to fill specific roles that the story requires.