In TOS 3rd season we could find in "Day Of The Dove" Kirk said to Kang: "For three years, the Federation and the Klingon Empire have been at peace. A treaty we have honored to the letter."
But I could not find the famous words of Dr. McCoy about 50 years hostilness :-(
The first appearence of Klingons in TOS was in the 1. season: Errand of Mercy.
Quote form the beginning: "Negotiations with the Klingon Empire are on the verge of breaking down. Starfleet Command anticipates a surprise attack. We are to proceed to Organia and take whatever steps are necessary to prevent the Klingons from using it as a base."
The fighting between federation and the empire was abruptly ended when the Organians intervened and forced an end to the conflict.
In Trouble with Tribbles, TOS 2nd season, Kirk asked "How close will we come to the Klingon outpost if we continue on course?" and Mr. Checkov answered "1 parsec, sir". After that Spock talked about the immediate past history of the quadrant: "Under dispute between the two parties since initial contact. The battle of Donatu V. was fought near here 23 solar years ago. Inconclusive [...disputed area...] Undeveloped. Sherman's Planet is claimed by both our federation and the Klingon empire."
TOS 2nd seasons is in the year 2266. Therefore the battle of Donatu V. was 2234.
We can also find an importent statement about the Klingons in the 6th StarTrek movie, when Spock says: "The dismantling of our space stations and starbases along the neutral zone. An end to almost 70 years of unremitting hostility, which the Klingons can no longer afford."
This was said 2295 or -2297 - and we have to count back 66-70 years. Therefore the hostility began between 2224 and 2231.
And in "First Contact" we can get the information from Riker, that centuries ago, a disastrous first contact with the Klingons led to decades of war.
This episode belongs to TNGs 4th season - that means the year 2367.
So at first there was a very bad first contact; and later on the relation got more and more hostile. Combined with Spocks statements above the First Contact is also the begin of the "cold war" with the Klingons!
