In a London music hall, Canadian Richard Hannay is watching a performance by the memory man Mr Memory when gunshots are fired and the audience disperses in panic. Outside, Hannay is accosted by a mysterious foreign woman, who invites herself back to his flat. The woman, who gives her name as Anabella Smith, eventually reveals that she fired the shots, to create a diversion to allow her to escape from two men who are following her. She is a spy working for the British government, seeking to prevent the transport of certain vital military secrets out of the country. She tells the sceptical Hannay of a sinister conspiracy, led by an enemy agent who has one identifying feature - he is missing part of a finger on his right hand. She must make contact with a man in Scotland if she is to have any hope of stopping the conspiracy.
Later that night, Hannay awakens to find the woman staggering over him, a knife in her back. She dies, clutching the map of Scotland, on which she has marked a remote village. Realising that he is now in danger himself, and that the police will suspect him of the murder, Hannay grabs the map and makes his escape, borrowing a milkman's uniform and cart to get past the enemy agents. He reaches King's Cross station seconds ahead of his pursuers and boards a train headed for Scotland. When the train arrives in Edinburgh, Hannay learns that the body has been discovered in his flat, and the police are looking for him. The police board the train, and Hannay seeks to evade them by posing as a woman's lover, but the woman exposes him to the police and he is forced to flee.
Convincing the police that he has left the train, Hannay arrives at his destination and makes his way towards the village. On his way he encounters a stern and pious crofter. Posing as a mechanic looking for work, Hannay asks him if there have been any new arrivals locally. The crofter tells him of a professor who has taken a house in the next village, who Hannay takes to be the contact mentioned by Anabella, but it is already too late to get there before dark. The crofter reluctantly agrees to put him up for the night, for a price. However, he becomes suspicious of Hannay when he spies him talking to his young wife, Margaret. That night, Margaret sees the light of approaching cars and rushes to warn Hannay, but her husband follows her, assuming she is planning to betray him. Hannay offers him five pounds to keep his secret, but when the police arrive he looks set to give Hannay up before Margaret helps him to escape through the back, giving him her husband's coat to cover his own conspicuous jacket.
Hannay makes his way to the professor's house, where a party is in progress. When the guests have left, the professor takes Hannay to his study, where Hannay tells him his story. But the professor is the man with the missing finger, and he turns a gun on Hannay and shoots him. Hannay is saved when the bullet is stopped by the bible in the crofter's coat, and heads for the local sheriff. The sheriff does not believe his story, and Hannay is forced to break out of the office.
With the police in pursuit, Hannay sneaks into a political meeting, where he is mistaken for a guest speaker. After ad-libbing a rousing speech, Hannay is captured, identified by the same woman, Pamela, who earlier exposed him on the train. The two are taken by car, ostensibly to a police station at Inverary, but when it becomes apparent that they are heading in the wrong direction, Hannay takes advantage of the distraction of a herd of sheep on the road to make a getaway, with Pamela, now handcuffed to him, reluctantly in tow.
The two make their way to a boarding house, where at Hannay's insistence they pose as an eloping couple. Pamela refuses to disbelieve Hannay's story until she sees the two agents who are trying to track him down. Overhearing their conversation, she realises Hannay has been telling the truth.
When Hannay wakes, she tells him that she overheard the men talking about a rendez-vous at the London Palladium. Hannay is furious that she didn't wake him earlier and the two set off for London. As Hannay heads for the London Palladium, Pamela goes to Scotland Yard to alert the police, but they tell her that the Air Force report no missing papers. Frustrated, she leaves, but the police have her followed in the hope that she will lead them to Hannay.
At the Palladium, Pamela joins Hannay in the audience, with the police behind her. Hannay spots the professor in one of the boxes. When Pamela tells him that no papers are missing, Hannay is mystified, but remains convinced something is afoot when the compere introduces Mr Memory. Realising that this is the key to the whole conspiracy, Hannay asks Mr Memory what are the 39 Steps, but he is shot by the professor before he is able to complete his reply. The police catch the professor and, backstage, Hannay and the police manage to extract from the dying Mr Memory the details of the stolen military secrets. Relieved, Hannay and Pamela join hands, the handcuffs still swinging from Hannay's wrist.
