Originally the Script for the movie called for a Romulan Bird of Prey as it was the Romulans who were going to feature as the villians. As changes to the movie progressed they became klingons and they didn't change the ship concept. Therefore this is the first movie where klingons have both cloaking and birds of prey.Wasn't there one in The Motion Picture? (It's been a long time sense I've seen the movie, so I'm not to sure)The 23rd and 24th century variety didn't come into service until the 2280's.
Somebody remembered the Romulan-Klingon Alliance of ST:TOS "The Enterprise Incident" (specifically, that is, the fact of the Romulans using Klingon ship designs) and decided it went the other way, too. Even the Bird-of-Prey design which later became the H.M.S. Bounty of Star Trek IV: The Voyage Home had never previously been seen in Star Trek, prior to Star Trek III: The Search for Spock. In ST:TROS "The Enterprise Incident", the Romulans use both Klingon D-7s and the Romulan warbird design from ST:TOS "Balance of Terror" ProfessorTrek 05:56, August 14, 2011 (UTC)