The game created a completely different storyline and takes place on the Strogg Homeworld, of.. er, Stroganoff?
Shortly after landing on an alien surface, you learn that hundreds of your men have been reduced to just a few. Now you must fight your way through heavily fortified military installations, lower the city's defenses and shut down the enemy's war machine. Only then will the fate of humanity be known.
The strogg story continued in Quake 4, id have a thing about being completely out of sequence!