General Von Talon is a mean-spirited general who has a hatred for pigeons, and he also takes pleasure in eating his prisoners. He rudely calls Valiant a pipsqueak. He lost his left eye sometime during the war and wears an eyepatch. He and his minions' job is to capture homing pigeons that are carrying valuable information and bring them to their base: a huge fortified bunker on a sea cliff. Von Talon tortured his prisoners by forcing them to listen to Werner Bruggemann's Da Jodel Rudel. He stuffed and mounted the pigeons that he killed and placed them in his trophy room.
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.
Elsewhere, a small wood pigeon named Valiant is watching an Allied forces propaganda film in his local bar (an overturned rowing boat) in West Nestington. Wing Commander Gutsy, a war hero flies into the bar, informing everyone that signups are scheduled the next day in Trafalgar Square, London. In General Von Talon's lair, Mercury resists interrogation by his captors. Valiant flies off to London, bidding his mother and Felix, the local barman, goodbye. In London, Valiant meets a filthy pigeon named Bugsy, who is wanted by two thugs. In order to escape the wrath of the thugs, he signs up with Valiant.
The recruits, Valiant, Bugsy, Lofty, an intellectual red pigeon, and Toughwood and Tailfeather, two strong but dim-witted twin brothers, form Royal Homing Pigeon Service Squad F, and are sent to a recruit training facility. Under the command of Sergeant Monty, who declares that he will toughen them up for the RHPS, the training begins. Meanwhile, Von Talon and his henchmen, Cufflingk and Underlingk, try numerous attempts to discover the message's departure location. However, Mercury refuses to tell, so Von Talon and his goons resort to tortures to get Mercury to crack. First they try blasting him with Werner Bruggemann's Da Jodel Rudel playing over the intercom, but despite the loud annoying yodeling, Mercury still does not crack. Von Talon then injects Mercury with a truth serum. While Mercury tells the truth, he still refuses to actually tell them what they want to know, and instead babbles on and on, annoying them until he accidentally reveals the location: Saint-Pierre.
Throughout the training, Valiant develops a crush on Victoria, the camp's nursing dove. Eventually, Gutsy arrives and tells the Sergeant that the recruits need to leave the next morning, despite their training being vastly incomplete. Bugsy, however, decides not to go on the "highly dangerous" mission and flees the camp that night. The next morning, Valiant and the others prepare to leave and start to board the plane headed for France, but not before Bugsy shows up at the last second. The journey becomes extremely perilous, as the plane is caught in the midst of dogfight. Their plane sustains heavy damage and the pigeons soon have to bail out, in boxes equipped with parachutes. The pigeons are dropped from the plane; however a technical malfunction causes Gutsy's box to fail to deploy. The plane goes down in an inferno of flames, presumably killing Gutsy in the resulting explosion.
In France, the pigeons meet Charles de Girl and Rollo, two mice from the French Resistance, Mouse Division, the latter being an expert saboteur who lead them to Saint-Pierre, where they receive the message they have been ordered to deliver. They soon come under attack by Von Talon's henchmen, resulting in Bugsy and the message being captured. 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.
After a climactic chase by the falcon, Valiant hides in the cottage where he lives, where he is attacked by Von Talon again. With the help of his mother and Felix, Valiant finally defeats the villain by getting a giant hook caught on his medals, leaving him to be beaten senseless by the water wheel. It is unknown what happened to Von Talon after this, but he was presumably arrested.