Strife also had storytelling and some RPG elements and that was pretty early, still after System Shock though.

Nobody here has mentioned Pathways into Darkness. Although coming out in 1993, it was a year later than Ultima Underworld, I'd still say it deserves an honourable mention. I suppose it is less known because it came out on the Mac?

PS: it was created by Bungie, who you may know as later going on to make the Halo series :D.

Let me make a broader comment.

Video games have two main historical roots (which actually intersect if you look deep enough): RPGs and Wargames.

With Wargames the narrative aspects have always been extremely subordinate - although wanting dynamic campaigns, predefined scenarios, etc... does indicate what each individual may prefer in terms of narrative experiences even there.

With RPGs the tension between the ludic and the narrational elements was always stronger. The above mentioned Ultima Underworld and System Shock I see as first explorations of moving deeper into narrative after a huge domination of ludic aspects. Afterall an AI as DM just does not cut it in comparison to a good DM. The 1st person view in these I see as coincidental, technically undertaken to contribute in distancing from the traditional party based, character customization gameplay traditions. This breaking out from tradition was bound to happen in what was an at least 25 year old media, and given the options were that it could happen in arcade games, wargames or RPGS, no wonder to me where it happened.

With FPSs particularly some of the main precursors were already mentioned, like Half Life and the Dark Forces/Jedi Knight games. I would maybe mention also NOLF and MDK, whereas Deus Ex had more of an RPG pedigree rather than action shooter in my opinion. Still this was only part of a wave that touched on other genres, think of Starcraft and Myth The Fallen Lords to get a clear view on what I mean.

In RPGs of course the tension pretty much exploded, which to me is one of the reasons why the genre became pratically formless. The other genre to bring up is adventure games, where narrative always reigned supreme, and attempts to interject ludic elements usually fell flat with a huge portion of the audience. No wonder to me how adventure went into a decline as other genres usurped some of its competitive differentiators in terms of narrative gameplay.

I'll leave it at that, which should be around the early 00s. Obviously if you didn't play in the 80s and most of the 90s all of this is not going to say much, you needed to experience at least the early 90s to compare how the end of that decade was a huge shift over what came before. We are only now having a counter reaction to the onslaught of narrative experiences.

Please note the above is descriptive, no comment on the kind of ludic or narrative experiences I prefer.

Edit and PS: The above comment reminded me I wanted to say: The rise of narrative in gaming to me is owned by two names in particular, and they are not in FPS genre, Blizzard and Bungie.

I didn't mean to imply that cinematic storytelling was superior, just that it was a newer development in FPS games. System Shock tells its story via logs and environment, too, so maybe these are the missing links that I was wondering about, FPS games before 1997 that followed in System Shock's footsteps regarding the narrative? Not that they necessarily need to be connected, but apparantly they were coming up with similar ideas during the same time period.

Another good call, apart from Strife, already mentioned by Sbain_Stargem!

Probably. To tell the truth, I hadn't heard of it before ...

Also worth mentioning: Cybermage - Darklight Awakening (1995). It plays shooterish for the most part, but has some RPG elements (it's by David W. Bradley) and NPCs to talk to and story.

I liked that game quite a lot. It's a perfect example of the RPG to Shooter convergence given its author ;)

I think that was slightly too early for shooters to really go narrative heavy because they were absolutely dominated by multiplayer - for me personally that was something that got me away from FPS though I did enjoy stuff like Wolfenstein, Duke Nukem, Hexxen or Heretic.

Bungie with Myth already innovated the solution, but that was a cult classic. Blizzard were the ones that showed anyone with eyes to see that you could separate the narrative driven single player experience, from the pure multiplayer experience, and therefore serve two market segments with one common development investment. Roll in the dough - of course this is not discounting the production values of a company like Blizzard which were certainly high. From then on it was a matter of time until someone did it in FPS. Which was Valve of course, regardless of any other innovation precursors also in the FPS genre.

By the way, something that shows how FPSs were behind the curve are space action games. Look at something like Wing Commander, Privateer for action games with a strong narrative flavor - see how much earlier that happened than for FPSs. Of course in this case it's flight sims and therefore wagames that carry the pedigree instead of RPGs, which goes back to the dynamic campaign vs sculpted scenarios distinction I mentioned higher up.

Still I'd say a Wing Commander has more in common with for example Hitman than it does with Elite when you look at the gameplay structure you are mastering. And the tension between sandbox (dynamic campaign) and mission narrative is alive and well in the 3D "FPS" genre - by which I mean GTA likes.

Can't say what the first game(s) might have been, but for me the first game to take it to a whole new level of story telling integrated into the gameplay in an epic fashion was Halflife. That game really raised the bar IMHO.

Quickly skimming the posts in the thread though I can see some other titles mentioned such as the Wing Commander games and others that I'd have to say are pretty high up there also. What's going to be a bit of fun perhaps, is researching all of the games people suggest here and trying to hunt them down later to experience some new old things. :)

Maybe Half-Life was the first FPS to fully integrate the story-telling into the shooting parts by way of using scripted events for the game engine (e.g. people you can talk to and who ask you to follow etc.), instead of using cutscenes or different gameplay sections between levels, or instead of just creating a setting that can be explored or ignored (e.g. via logs and environmental messages)?

From what I've seen, I suppose it's true though that the Wing Commander games already did something similar by using (possibly scripted) voiceover comments during the shooting sections? I haven't played them myself. And I'm not really familiar with the games between System Shock and Half-Life like Realms of the Haunting and Strife yet to compare their storytelling approaches.

Half-Life. Sure, there were games which did it exceptionally well before, but Half-Life is the game which has really popularized this particular trend - and also started the trend of linear, heavily scripted shooters.