В течение четырёх лет после событий Brood war, Зерги не нападали на поселения терранов и протоссов, и об их деятельности не было известно: все разведывательные корабли, отправленные к планете Чар, исчезали, так и не доложив о том, что успели узнать. Таким образом, Терраны и Протоссы могли лишь догадываться о том, чем занималась Королева клинков — новая предводительница роя Зергов — в течение этих 4 лет.

Действие игры начинается на планете Мар Сара, где Джим Рейнор начинает восстание против Доминиона. Там он встречает своего старого знакомого, Тайкуса Финдли, который получил свободу в обмен на работу в организации «Фонд Мебиуса». От  Тайкуса Джим узнаёт, что Доминион и фонд ищут некие артефакты пришельцев, и Тайкус предлагает Рейнору работать на фонд, который обещает вознаграждение людям, нашедшим их. На Мар Саре они перехватывают у Доминиона один из артефактов, но неожиданно на планету нападают зерги. Тайкус, Рейнор и его люди успевают покинуть Мар Сару и узнают, что зерги под предводительством Королевы Клинков начали наступление на Доминион. Рейнор продолжает искать артефакты, по ходу дела выполняя другие миссии, и захватывает старого компьютерного адъютанта, у которого есть запись приказа Менгска о начале включения пси-эммитеров — устройств, привлекающих зергов — на бывшей столицей Конфедерации, Тарсонисе. Захватив межгалактический телеканал UNN, Рейнор пускает в эфир эту запись, что поднимает бунт на многих планетах и сильно расшатывает верность граждан императору.

Неожиданно во время полета на Гиперионе Рейнор встречает Зератула, которому открылась страшная правда — некая сила вскоре уничтожит всех живых существ во Вселенной. Зератул рассказал, что первым такое будущее увидел Сверхразум зергов и нашел единственное спасение в лице Королевы Клинков.

Добыв последний артефакт и прибыв в точку встречи с кораблями «Фонда Мебиуса», Рейнор натыкается на три корабля Доминиона. Рейнор идет на абордаж, желая встретить и убить Арктура Менгска, но неожиданно для себя он встречает наследника трона Доминиона — принца Валериана Менгска. Тот рассказывает, что является хозяином «Фонда Мебиуса» и нанял его для поиска артефактов. Чтобы окончательно убедить Рейнора и перетянуть его на свою сторону, Валериан сказал, что он может дать Рейнору шанс спасти Сару Керриган. И, хотя союзники Рейнора ждали от него продолжения в восстании против Доминиона, он решает отправиться на Чар. В ходе ожесточенной битвы терраны побеждают и задействуют артефакт. К Керриган возвращается человеческий облик, но она чуть было не становится жертвой Тайкуса, который, как оказалось, по приказу Арктуруса Менгска хотел убить её в обмен на свободу. Но Рейнор спасает её, прикрыв от пули своим скафандром, затем он вырывает револьвер и убивает старого друга.