In May 1944, 5 years since the declaration of World War II, three Royal Homing Pigeon Service war pigeons are flying across the English Channel with the White Cliffs of Dover in sight, carrying vital messages to Great Britain. Despite the poor weather conditions the pigeons have nearly reached their destination. They are, however, suddenly ambushed and attacked by a German enemy falcon called General Von Talon; two of the pigeons are instantly killed, yet the third, Mercury is taken as a prisoner of war.
Von Talon and his henchmen, Cufflingk and Underlingk, try numerous attempts to discover the message's departure location. However Mercury refuses to tell, despite the tortures inflicted upon him, such as irritating him with yodelling music from Austria and injecting him with truth serum, before Mercury accidentally reveals the location: Saint-Pierre.
In Saint-Pierre, France, Underlingk and Cufflingk capture Bugsy and the message. Von Talon takes the message from Bugsy and decides to cage him up and eat him later. Valiant and the troops follow Bugsy to the falcon's bunker, where they discover that Gutsy has survived the plane crash. Valiant takes advantage of his small size and sneaks into the bunker through the gun barrel, retrieves the message, and frees Bugsy and Mercury. Unfortunately, the falcons are alert and give chase. As Gutsy and the others fend off Von Talon's henchmen, Valiant flies to London to deliver the message, followed closely by Von Talon.
It is unknown what happens after Underlingks and Cufflingk's defeat, but they are presumably arrested.