The Phaedans had a civilization that was comparable to Earth's Roman Empire. By the 2230s, had split into two races; the blue Phaedans and the black Phaedans who called themselves the Shadow that became the dominant species. The Shadow then started a genocidal war against the blue Phaedans, committing atrocities such as eating and enslaving children.
The Federation Starship USS Enterprise under Capt. Robert April did the first survey of Phaedus and the Phaedans in 2239, knowing that it would be several thousand years before they would make first contact with them. However, after witnessing the aforesaid attrocities, Capt. April faked his death and decided to violate the Prime Directive to help the blue Phaedans against the Shadow. April was able to give the blue Phaedans enough Starfleet technology to mount a counter-offensive against the shadow to prevent their annihilation. For twenty years, April led and proctected the blue Phaedans against the Shadow with supplies and support from Section 31 through a trader named Mudd.
However, some time between the 2240s to at least 2259, the Shadow made contact with Klingon Empire. The Empire supplied the Shadow a number of their weapons and technology to defeat April and the blue Phaedans. The Klingon saw supporting the Shadow as way to expand their empire and to defeat their real enemy, the Federation. In 2259, following Capt. Kirk's arrest of Capt. April following his attempted theft of the new USS Enterprise, the Phaedans became part of the Klingon Empire.(TOS - Countdown to Darkness comics: "Issue 1", "Issue 2", "Issue 3", "Issue 4")