After the destruction of several Romulan outposts near the Romulan Neutral Zone he was sent to investigate the possibility of Federation involvement. In order to do that he needed to cross the Neutral Zone in 2364. Tebok and Captain Jean-Luc Picard each thought the other responsible for the attacks that wiped out both Federation and Romulan outposts. At first, the meeting threatened to escalate into conflict. Once both Picard and Tebok admitted that neither had attacked the outposts, Tebok and Picard made a limited agreement to share information about the destroyed outposts. (TNG: "The Neutral Zone")
Background information Edit
Tebok was played by Trek regular Marc Alaimo.
This character's name was devised by Eric A. Stillwell, on Maurice Hurley's request. (Information from Larry Nemecek) "TAY-bok" was the pronunciation for this character's name from the script pronunciation guide. 
In later episodes, it was established that not the Federation but the Borg were responsible for the destructions of the outposts.
In the novel Exodus, the first of the Star Trek: Vulcan's Soul trilogy, Tebok attends a secret meeting concerning the threat that had destroyed bases along the Romulan and Federation border. Interestingly, amongst the Cardassian representatives is Gul Akellen Macet, who was also played by Marc Alaimo.
His mirror universe counterpart (β) appeared in the novella "The Worst of Both Worlds". He was the commander of the Romulan Warbird Gath'thong. In September 2371, his ship was destroyed with all hands by the Klingon-Cardassian Alliance Galor-class warship Hebitia which was under the command of Gul Madred. The Hebitia was able to catch Tebok's crew unawares as it was equipped with a Klingon cloaking device.
In the backstory to Star Trek Online Tebok had been promoted to general by 2386 and became deeply involved in the reconstruction of the Romulan Empire following the supernova of 2387. He frequently clashed with Admiral, later Praetor Taris politically, up to and including refusing a direct order to put down a rebellion on Kevratas by force in 2397. In 2399 he was killed when his starship IRW Alth'lndor was infected with a computer virus (implied to be from an Iconian probe) and suffered antimatter containment failure.