http://en.wikipedia.org/wiki/Warhammer_40000

While I know Wikipedia isn't the best source to quote, it's fairly accurate on most things.

Warhammer 40,000 was first published in 1987 and evolved pretty quickly afterwards.

The first mention of the alien lifeforms known as the Tyranids (what the zerg are "based on") was in 1990, earning their own full-fledged Codex (army rulebook) in 1993, which predates Starcraft planning development stages by 2 years and Starcraft release by 5 years.

True enough.