In the mid-24th century, the Tzenkethi fought a war with the United Federation of Planets. Amongst the starships involved was the USS Okinawa, under the command of Captain Leyton, who had fought against a number of Tzenkethi raiders. (DS9: "The Adversary", "Paradise Lost")
In late 2371, a Founder posing as Federation Ambassador Krajensky informed Captain Benjamin Sisko that the current Tzenkethi Autarch had been deposed. He ordered the USS Defiant to the Federation-Tzenkethi border to reinforce the Federation presence to the new leading faction. However, the entire mission was actually engineered by the Dominion to incite another war between the two powers; there never was a coup d'etat. After his identity was exposed, the changeling commandeered the Defiant and attempted to attack the Tzenkethi settlement on M'kemas III, though he was stopped before the Defiant reached the planet. (DS9: "The Adversary")
Background information Edit
The Tzenkethi have never been seen on-screen. It was unclear if they were a humanoid race or not.
Robert Hewitt Wolfe said in December 2006 that he thought that he had named the Tzenkethi by combining the name Kzinti (from Larry Niven's race of aliens that appeared in the animated series episode "The Slaver Weapon") with Tsankth, after a race from the RuneQuest and HeroQuest RPGs. Wolfe also said he did not picture them as cats like the Kzinti, but as being like the Hakazit from Jack L. Chalker's Well of Souls novels. He saw the Tzenkethi as being "heavily-armored lizard things". 
According to Star Trek: Star Charts (pg. 36), the Tzenkethi government was named the Tzenkethi Coalition. The capital of the Coalition was located in the Tzenketh planetary system. This system consisted of a primary and at least one planet. The primary was named Tzenketh. This was a Class M star with a magnitude of +9.
Tzenkethi were also referred to in the novel Articles of the Federation. They join the Typhon Pact (β), an alliance of non-Federation powers, in the novel A Singular Destiny. Several Tzenkethi characters appear in the Star Trek: Typhon Pact novel Rough Beasts of Empire. In these novels, they are described as being humanoid in shape, and extremely attractive to many different races. Because of their internal biology which is effectively various fluid-filled sacs, they have a very fluid movement. Their skin pigmentation apparently ranges across the entire visible spectrum, in addition to having a slight phosphorescent glow. Bioluminescence is also common on the Tzenkethi homeworld. The later Typhon Pact novels Plagues of Night, Raise the Dawn, Brinkmanship, the eBook The Struggle Within and the DS9 novel The Missing also feature Tzenkethi characters.