The Klingon Alliance (usually Klingon Empire) was a military group formed to combat the Ultari Empire and the Federation. The four races are the Klingons, Letheans, Gorn, Orions Nausicaans, Ferasans and Frugl. These races joined forces after discovering that Ultari agents had been integrating themselves into these governments. They all managed to discover this just in time, and joined forces against the Ultari.
In 2408, the Klingon people were led from the Federation by K'hallA, daughter of K'Gram, who restored the warrior-society and faith in Kahless that her people had lost in their union with the Federation. However, the newly-freed Klingons didn't have the military might or resources to maintain a long-term conflict with various enemies (the Federation and the Ultari being two such).
One of K'hallA's companions, a Gorn named Krall, suggested making alliances with other warrior-races in order to strengthen their position. The Gorn Hegemony, the Orion Syndicate and the Nausicaans were among the first to answer the call to arms against the Federation and in 2409, they formally adopted the name "Klingon Alliance."