As far as I'm concerned, story comes first.
That's just because you can almost do endless worldbuilding (worldbuilding.se has countless examples of all the aspects you can consider while doing so) without sketching out a single plot line, or character arch.
It's true that if you are a very descriptive kind of writer you can start your novels with wide descriptions of your setting, but sooner or later you'll need to start the plot somehow.
Worldbuilding surely does back up your story and helps build your characters, but it's the plot that propels the story forward.
Consider a simple plot line:
- little red riding hood has to bring food to her sick grandma
- she needs to cross the wood
- the wolf tricks her
- eventually, an hunter saves the day
It's really scarce, but it's an example of basic storytelling, and it's what humans have done for centuries. As childish as it is, it works. From the worldbuilding perspective, we could expand indefinitely any of those aspects:
- Who are those characters? Where do they live?
- Why does the wolf talk? Do other animals talk, too?
- What creatures and plants inhabit the wood?
- What's the background of the hunter?
We could (possibly) spend hours imagining a whole nation containing Red's house, the wood, and the grandma's house, going so far as adding politics, intrigue, magic and so on.
But without a basic plot, this is just drawing a map without a clear idea of where you are going. Per se, that's nice. Half the fun of worldbuilding, to me, is imagining what kind of characters or stories my world could support.
But again, even if worldbuilding gives you plenty of possibilities and interesting concepts, you'll eventually have to focus on some plot. If you start a book there is only so much you can go on without giving the readers some hint of what the plot will be. Let's take for example the Lord of the Rings: the first chapters are very descriptive, the story starts slower than we are used to by modern standards, but in the end we get that there's this hobbit and he'll start a journey.
Contrarywise, even the most compelling plot needs a bit of worldbuilding, or you'll risk being a bit unrealistic or not immersive enough. But I dare say that plots can live on their own.
So, to me, if writing a story was like riding a car, the plot would be the engine and the wheels, and the worldbuilding would be everything else. I wouldn't like to drive the most powerful engine without any bodywork, and I wouldn't like to have the most beautiful car without any engine inside.
So, just do both - but if you have a good incipit for the plot, don't let the lack of a complete worldbuilding drag you down.