The first "Bird-of-Prey" seen was in TOS: "Balance of Terror" and was of the Romulan variety. As originally conceived, the Klingon variant of the Bird-of-Prey was actually a Romulan ship; the script of Star Trek III at first called for the film's main villains to be Romulans using a Romulan Bird-of-Prey, as had been typical of Bird-of-Prey use in Star Trek: The Original Series.
In the chronology of the Star Trek universe, the term "Bird-of-Prey" was first referenced on Enterprise in "Sleeping Dogs", and may have been implied to be the "two ships approaching at high warp" at the end of that episode. An earlier reference made in "Broken Bow" to "a fleet of warbirds" was mentioned by Brannon Braga as a mistake, implying that the production team only wished Romulan ships to be identified as warbirds.
In the game Star Trek: Legacy, the Bird-of-Prey is available as a ship for the player to control.