You should take the process by phases or stages. If you have already built your vertical slice proof of concept, then it's time to plot out the storyline so you can break the game down into scenes, then start building those one by one. If you have not yet built a proof of concept / vertical slice, that's definitely where you need to go next.

Proving that the gameplay is fun is usually the first order of business. A gameplay prototype (likely with entirely placeholder/programmer art) is the most straightforward way to prove that - before you invest a bunch of time in art/story/etc. After all, if the gameplay turns out not to be fun, you'll have to change it, and that may require changes to the art/story/etc too!

My feeling is that the answer may depend on what sort of game you're making, and specifically on how those elements fit into it.

So for example:

If you're making a story-light action-game, or your core experience relies on as-yet untested mechanics, then it might be wise to focus on developing and testing the gameplay.

Conversely, if you're making a story-heavy point-and-click adventure or “walking sim”, then it may perhaps make more sense to focus primarily on the plot and characters.

And so on for other cases!

swiftcoder said:
After all, if the gameplay turns out not to be fun, you'll have to change it, and that may require changes to the art/story/etc too!

I would argue that, for some games, the opposite might turn out to be true: that work on the story might incur changes to the gameplay.