Minecraft doesn't have (much of) a story, but it does have progression, which is just as important in a sandbox game

Story is one of the easiest ways to add progression, but it's not the only way.

That's not to say story is bad but you can have quite good games without it, and any "long lasting/replayable" game has to have gameplay that stands alone.

People will put up with crappy gameplay for an amazing story, but they're not going to replay it much.