Stationed on the flagship carrier Qel'Ha, Mess'Ta and the rest of the fleet spent decades searching without result, only to detect a signal on the planet of Bhekar Ro—one of xel'naga origin. The fleet thus headed for the planet. With his superior, Executor Koronis, going planetside with a large force, Mess'Ta remained onboard the carrier, only to detect a large zerg force heading towards the planet. Per Koronis' instructions, Mess'Ta led the protoss fleet against the zerg and upon their arrival, a terran Alpha Squadron fleet. In Koronis' mind, he could not have left the Qel'Ha in better hands.
For all his efforts, they were in vain, as on the surface, a strange creature was released from a xel'naga temple. It wiped out all the ships above the planet, including the Qel'Ha and those aboard it.