Pelin tarina sijoittuu neljä vuotta ''Brood War''-pelin tarinan lopun jälkeen. Kolmen lajin taistelu jatkuu edelleen.
Pelin tarina sijoittuu neljä vuotta myöhempään aikaan kuin ''Brood War'', jonka lopussa [[Sarah Kerrigan]], [[zergit|zerg]]ien kuningatar nousi maailmankaikkeuden hallitsijaksi. Taistelu voimasta ja rauhasta jatkuu edelleen kolmen lajin välillä (Terranit, [[protossit]] ja zergit). Peli alkaa kun Raynor tapaa vanhan kaverinsa Tychus Findlayn ja he alkavat keräilemään niin sanottuja Artifacteja. Pelin lopussa Artifact Tuhoaa Kerriganista sen Zerg osan ja kerriganista tulee taas ihminen. Tychus yrittää tappaa kerriganin koska hänen puvussaan on pommi, koska hän teki sopimuksen Arcturus Mengskin kanssa hänen tuli tappaa kerrigan niin hän pääsisi eroon pommista. hän ei pystynyt paeta puvusta. Viime hetkellä kun Tychus oli ampumassa Kerrigania Raynor suojasi ja ampui Tychusia on vielä epäselvää kuoliko Tychus varmasti.
