Cooperation between the Federation and the Klingons was foreshadowed in their first appearance in Errand of Mercy. When the Organians stop the war between them, Ayelbourne says to Kirk and Kor that in the future, "You will be fast friends. You will work together." So TNG showed one step in the evolution of their relationship.
Another thought occured to me about the Klingon Empire. In a DSN ep, Ezri Dax observes that the Empire is dying -- the whole corrupt group, at that time embodied by Gowron. At some point, the Klingons will actually become a real part of the Federation, not just treaty partners, perhaps after some big upheaval in Klingon society.
Red Ranger