Nope. Many campaigns are merely setting and NPCs and the story comes only after the PCs interact with the environment and its inhabitants. I refer to this phenomenon as Schrödinger's Plot; until the game is played, there's no real way to know what is the actual story. It has the added benefit of ensuring the players are well-invested in the campaign.
Let's not bag on the OP's use of the word Story. He may not have meant it as a railroad, which some people equate Story=railroad. He certainly could review your proposal of a sandbox campaign and point at elements and say "that's Story, just like I said" that aren't the example of Shrodinger's Plot.
Even Shrodinger's plot has pitfalls. Celebrim had a whole list of Shrodinger's Products and the pros/cons of each.
And even in a sandbox, you've got to setup hooks, motivations, background stuff for the NPCs for their to be anything interesting to catch the PC's eye. If he beams into the sandbox and no NPC is doing anything, there's not going to be a lot of interaction going on. The initial setup of the NPCs current projects, motivations, background may in effect be identified as "story" to the OP.
Personally, I set up Story as a bi-directional process. I identify what's important to the players and make plot hooks that would appeal to them. The players pick one to pursue, and I write material to tell that story. So I'm not forcing My Story on the PCs about rescuing a princess, I'm turning the PC's mundane goal of clearing out the mine into a Story about the PC.
There's extreme cases of sandboxism where the GM eschews story so much, that everything the PC does is a boring simulation. A good GM makes whatever the PCs want to do be fun and dramatically entertaining. I call that Story.