There were already a lot of FPS around that era that had a proper story.

Can you provide some examples? I don't remember Turok or Unreal having gripping stories.

Pathways into Darkness (1993), Marathon (1994), Marathon 2: Durandal (1995), and Marathon Infinity (1996) all precede Half-Life (1998).

https://en.wikipedia.org/wiki/Pathways_into_Darkness

https://en.wikipedia.org/wiki/Marathon_Trilogy

The stories of these games have been the subject of discussions for many years.

http://pid.bungie.org

http://marathon.bungie.org/story/

You may know Bungie as the studio behind Halo: Combat Evolved (2001) and subsequent games.

Marathons are awesome games still. It’s kinda sad that most of the PC players missed them. If my memory serves me right, only Marathon 2 was publishes on Windows quite late and it got bad reviews because of Quake and its 3d graphics. Marathons had bitmapped NPCs instead of 3d models.

Before Microsoft bought Bungie, They open sourced the Marathon code and gave the game data for free. Luckily people have been working on bunch ports for modern OSes:

https://alephone.lhowon.org/

Beside the Bungie games mentioned, there were tons of others. The first two Dark Forces, System Shock, Goldeneye just off the top of my head - all released before HL.