Milchmann, a henchman employed by STENCH (Society for the Total Extinction of Non-Conforming Humans), steals a secret chemical formula from a military laboratory. The British secret service has thirty-six hours to recover it before it passes into the hands of STENCH's leader, the evil Dr Crow. With no other experienced personnel available, they send Desmond Simpkins, their least competent agent. He is accompanied by probationary agents Harold Crump, Charlie Bind and Daphne Honeybutt, who has a photographic memory.

The four agents head for Vienna, where Milchmann has been spotted. They travel separately and are contacted individually by local field agent Carstairs and told to meet at the Café Mozart. When they get there, they initially pretend not to know each other. It soon becomes apparent, however, that the opposition know who they are and plan to get rid of them., Disguised as a waiter, Carstairs approaches Milchmann and tries to retrieve the secret formula, but is continually foiled by Simpkins' interference. Milchmann is there to meet another agent known as the Fat Man, but their communications are intercepted by Simpkins. The agents learn that the two STENCH members are to rendezvous at a warehouse at midnight. Daphne is knocked out when their drinks are drugged. Simpkins and Bind create a diversion while Harold takes Daphne back to the hotel. The two are clearly drawn to each other, but Harold eventually decides to go join the others.

Bind and Simpkins join Harold at the warehouse and, with great difficulty, they manage to get inside, to discover that the Fat Man has taken the formula and shot Milchmann. Before dying, he tells them that the Fat Man is heading for Algiers. The four spies head to the Kasbah and are able to track him down thanks to Daphne's photographic memory. They follow him to a brothel and Harold and Daphne are able to gain admittance by disguising themselves as women from the local harem. She manages to get close enough to him to get the formula but they are interrupted by Carstairs, also in disguise. He takes the formula, but Simpkins and Charlie arrive. Not realising who Carstairs actually is, they regain the formula and flee.

Simpkins and the others board the Orient Express and head home. In his room Simpkins finds Lila, who he'd previously seen singing at the Café Mozart. She is also in the employ of Dr Crow, but he manages to elude her. Daphne memorises the formula and they destroy it, before being captured by Lila and the Fat Man.

They are taken to the secret underground headquarters of STENCH. Daphne is taken to meet Dr Crow and the others are placed in a cell. Dr Crow tries various torture methods, to no avail. Daphne then hits her head by mistake and gives the details of the formula, which Dr Crow records on audiotape. After several unsuccessful attempts, the others manage to escape, rescue Daphne and steal the tape. The four agents take refuge in the bowels of the lair and are trapped in a mining machine. Just as they are about to be dipped in acid, Lila makes Dr Crow reverse the machine. Lila and the four agents escape after pressing the auto destruct button. Lila tells Simpkins that she is actually an agent with SNOG (Society for the Neutralisation Of Germs). They take a special lift directly to the office of their chief, who is debriefing a distraught Carstairs. Belatedly they realise that the lair must be placed directly below the office, which is also destroyed in the explosion. Harold and Daphne embrace.