You're probably confusing where the story is.
> I've only seen games that are interrupted by story.
A common misconception is that "story" in a video game is like a movie or book. A video game may also contain storytelling in the style of a movie" or book, but that's not what I'm referring to. Interactive storytelling in a video game is the mechanics.
In addition to [1] in my post above, I strongly recommend watching this[4] Extra Credits video about narrative mechanics, which discusses the story of the classic game Missile Command. Maybe you don't like the story, or you think it's simplistic, but it's still a story. Missile Command is inherently a story about the futility of war. Video games are an interesting medium for storytelling because they get you, acting as an actor in that story, to realize some aspects of the plot on your own. Everybody that plays Missile Command realizes the futility of the situation without having to be told that directly; it comes from the mechanics directly.
For a very good example of a more detailed story that is told primarily through the mechanics, I highly recommend playing Undertale[5]. The story in Undertale cannot be told in a non-interactive medium. A movie or book telling the same story can tell part of the story, but it would be a different story that wouldn't have nearly the same impact.
[4] https://www.youtube.com/watch?v=JQJA5YjvHDU
[5] DO NOT watch or read anything about the game first. I'd even recommend against even watching the trailer. Undertale has a serious problem with spoilers, and like a traditional "who did it" murder mystery, you should experience it as the author intended.
