Since the end of the Occupation, the social structure of the Cardassian home world, Cardassia Prime, had been slowly falling apart. A civilian based queue had rebelled against the Obsidian Order (the government of Cardassia) and came to power. The Klingons believed that the new government was being controlled by Changeling infiltrators, and they attacked Cardassia Prime with a fleet of their warships that had been stationed at Deep Space Nine. Captain Sisko requested that Lieutenant-Commander Worf (the only Klingon in Starfleet) be assigned to the station temporarily, in order to convince the Klingons that there were no Changelings on Cardassia Prime. Worf felt that the Klingons were only attacking the Cardassians as an excuse to regain their warrior grandeur after maintaining two decades of peace with the Federation. Sisko, the senior officers of DS9, and Worf, took the Defiant to stop the Klingon fleet and to save what members of the Obsidian Order they could. After saving almost the entire Order,including Gul Dukat, Captain Sisko was forced to fire on the Klingon fleet; ending over twenty years of peace between the Federation and the Klingon Empire. The Obsidian Order members were given a blood test by Doctor Bashir (Deep Space Nine's Chief Medical Officer) to prove that they were not Changelings (the blood would revert to its gelatinous state if they were). They were all who they appeared to be, but the Klingons didn't care. They said that they thought an Alpha Quadrant without the Cardassians would be a safer place. Sisko managed to convince Klingon Chancellor Gowron that the Dominion was planning to throw the Federation, Klingons, and Cardassians into war which each other so that they would be able to take over the Alpha Quadrant. Gowron agreed and stopped his attacks, but the Klingons refused to give up any Cardassian territory they had gained. Worf decided to stay on Deep Space Nine as its Strategic Operations Officer.
After the Klingon's paranoia had settled, it was the Federation's turn to watch their backs. An explosion at a Federation-Romulan diplomatic conference on Earth had apparently been caused by a Changeling. Captain Sisko and Odo took a runabout to Earth to train Starfleet officers in how to find Changelings apart from humanoids, and to install various Changeling detecting systems throughout Starfleet Headquarters. Blood screening measures were going to be implimented on all high ranking Starfleet officials. After the measures were in place, a Changeling in the form of Chief O'Brien (Deep Space Nine's Chief of Operations) came to visit Sisko and tell him that the Founders' plan was to use paranoia and fear to turn the Federation members against themselves.
Season four ended when Odo was infected with a bizarre disease that prevented him from maintaining a solid form. He returned to the Founder home world to see if he could be cured, and the Female Changeling he met before told him that he had been infected intentionally, to bring him back to their world. There he would face his judgement for killing one of his own people a year before. He went into the Great Link (an existence in which all Changelings merged together in their natural gelatinous forms) to be judged and emerged from it as a Human, no longer a Changeling. It was to be his punishment. Odo returned to Deep Space Nine to see a transmission from Klingon Chancellor Gowron declaring war on the Federation. Odo believed that when he was in the Link, he could sense that the Klingon High Council was being influenced by Changeling infiltrators.