Eh, I'd argue that they're equally important depending on the genre. Warcraft Orcs and humans was polishing the entire RTS concept of the day, so a token story about some random demonic horde (remember when they were literal demons?) invading a world was all they needed.
In an RPG setting, I think story is much more important (please note that I didn't finish that sentence with "than gameplay").
No, the foundation of every game isn't story, thats a blanket statement and every blanket statement is wrong. But pretending that story isn't important for any game is equally fanciful. (Also note that said stories don't need to be complex, or even good. Just catchy or interesting enough to make you care about the characters, world, quest, whatever.)