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. However, they are 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 the 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, Toughwood, and Tailfeather, two strong but dimwitted 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, despite the tortures inflicted upon him, such as irritating him by playing Werner Bruggemann's song, Da Jodel Rudel over the intercom and injecting him with truth serum, before Mercury 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 and vulnerable, 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.
It is unknown what happens after Cufflingk and Underlingk's defeat, but they were presumably arrested.