In late 2259, the G'Tok was scouting for potential targets in enemy space when forces of the Centauri Republic attacked the Narn Homeworld. After the Centauri drove the Narn government to surrender, the G'Tok and its crew became fugitives. They were hunted by Centauri forces for months before they finally arrived at Babylon 5. The ship's captain, Na'Kal, asked Earthforce Captain John Sheridan for sanctuary and assistance with repairs. Sheridan agreed to this request.
At exactly the same time, representatives from the Earth Alliance were negotiating a non-aggression pact with the Centauri. Word of the cruiser leaked out to Frederick Lantze of the EA Ministry of Peace, who in turn informed Centauri ambassador Londo Mollari. Mollari contacted his government, which responded by sending a Primus class battlecruiser to capture the G'Tok. When Sheridan refused to hand over the G'Tok, the Centauri cruiser opened fire on Babylon 5. The station and its Starfury squadrons returned fire and destroyed the cruiser, allowing the G'Tok to escape. The incident caused a severe but brief rupture in diplomatic relations between the Earth Alliance and the Centauri Republic.
Remnants of the Narn Fleet not destroyed or captured by the Centauri eventually joined the struggle against the Shadows led by John Sheridan, with the heavy cruiser G'Tok in particular playing a pivotal role in an early engagement in 2260. Needing ships to aid in the defense of the station, Captain Sheridan and G'Kar invited the G'Tok to come to the station. G'Kar met with Na'Kal and discussed postponing an open strike against the Centauri so that the G'Tok could provide escort to the White Star. Na'Kal refused, feeling it would surely be a suicide mission and not wishing to risk one of the few Narn vessels still functioning. After Sheridan embarks on the mission, Babylon 5 security chief Michael Garibaldi angrily confronted G'Kar about not forcing Na'Kal to go forward. Persuaded by Garibaldi, G'Kar convinced Na'Kal and a host of other League of Non-Aligned Worlds members to mount a small task force and rescue Sheridan. In the combined attack, the G'Tok and the White Star managed to destroy a Shadow vessel.