England’s greatest consulting detective, Sherlock Holmes, and his faithful friend Doctor James Watson, are returning from a holiday in Vienna when their train -- the Orient Express -- is flagged down by a carriage occupied by Pope Leo XIII. Potentially dangerous books have been stolen from the secret Library of St John the Beheaded, a Catholic repository of forbidden texts which is located in England so the Vatican can deny its existence. Holmes agrees to take the case, and upon returning to England he and Watson visit the Library, in the heart of St Giles’ Rookery -- a den of vice and squalor which Holmes notes seems less crowded than usual. The Library itself is a sequestered, underground building, designed such that a single entrance provides all of the ventilation it requires; this entrance is guarded day and night by two rival criminal gangs, who would like nothing better than to catch the other out in a mistake. As Holmes examines the scene of the crime and studies the list of visitors who had recently requested the stolen books, Watson observes a hooded figure entering a private reading room, and meets an oddly-dressed little man reading a copy of Redvers Fenn-Cooper’s autobiography.

Having tested the Library’s security and found it adequate, Holmes and Watson return to their lodgings in Baker Street, where the odd little man from the Library is waiting for them. He identifies himself only as “the Doctor”, confirms that he is one of the people on Holmes’ list, and claims that the books were stolen in order to prevent him from reading them. Whilst accepting that he is a suspect, he nevertheless suggests joining forces to bring the matter to a speedy conclusion. Holmes accepts, but is disconcerted by his inability to deduce anything about the Doctor; he is unable even to identify the mud on the Doctor’s trouser cuffs, which the Doctor claims is from Menaxus.

While Holmes pursues another avenue of investigation, the Doctor and Watson visit one of the others on the list, Mrs Kate Prendersley. Outside her home, they catch a glimpse of something in the shadows -- something like a sack of water suspended in a frame of stilts, which vanishes when they try to get a closer look. Mrs Prendersley explains that she has been investigating her husband’s death; he was apparently an innocent victim of the Trafalgar Square riots, but she believes that he had stumbled across a conspiracy and was murdered to prevent him from investigating further. She attempted to follow up her husband’s researches in the Library, but has found it a disturbing place; once, she believes, she saw the shadow of a man eating a book. She tries to quote the evil-sounding syllables which her husband had scribbled down in his notes, but as she does so, she bursts into flames and dies within seconds. The Doctor convinces Inspector Macdonald of Scotland Yard to write it off as a case of spontaneous human combustion, and leaves the shaken Watson to return to Baker Street.

Meanwhile, Holmes visits the seamier parts of London to investigate the two men who were guarding the Library at the time of the theft. While undercover, he witnesses a fight to the death between three trained dogs and a three-legged, reptilian “giant rat” from Sumatra, a creature like nothing he has ever seen on Earth. The two Library guards are brought before their respective leaders, Mr Jitter and Mack “the Knife” Yeovil, to explain themselves, and although they insist that they are innocent they have their hands cut off as punishment for their failure. Holmes is spotted as an impostor, but manages to escape from the angry crowds around him and returns to Baker Street to ponder these events.

The next morning, Holmes and Watson are summoned to the Diogenes Club by Sherlock’s elder brother Mycroft, who has a bone to pick with them. The Diogenes is in fact a front for Britain’s secret service, and the Queen is upset that the Pope has chosen to hire a private detective rather than come to her own intelligence service for help. Mycroft peruses Sherlock’s list of names, and as he discusses them with Sherlock, Watson comes to suspect that the brothers are hiding something from him. Most of the people on the list are members of the Diogenes Club, and one in particular, Baron Maupertuis, is already suspected of making shady business deals in his desperate attempts to make a name for himself in Victorian society. Mycroft summons the Baron to speak with Sherlock, but Maupertuis gives nothing away and they have no pretext to detain him further. As Maupertuis departs, however, Watson notices a figure waiting for him in a hansom cab outside -- the same hooded figure he saw earlier in the Library.

Mycroft learns Maupertuis’ destination from the club’s doorman, and shows his brother and Watson to a secret underground pneumatic railroad which is used to smuggle dignitaries out of the Club after clandestine meetings. They arrive at their destination moments too late to identify Maupertuis’ companion, but Holmes realises that they have entered a child brothel and pretends to be a client in order to get inside. He then leads the horrified Watson to an empty room in order to eavesdrop on Maupertuis, whose unknown companion is here for a séance with the notorious Madame Sosostris. Holmes and Watson hear the medium and the hooded figure chanting, and as the chant starts to develop an oddly compelling rhythm a strangely chilling third voice joins in. The figure warns the third voice that a detective and a man called the Doctor are interfering with their plans, and the third voice agrees to send more brethren through the gateway to render assistance.

Before Holmes can identify the hooded figure, he is spotted eavesdropping and is forced to flee. He and Watson are pursued by Maupertuis’ hulking, deformed bodyguard Surd, who proves to have the ability to incinerate people with the power of his mind -- as Watson very nearly fatally discovers before one of the brothel’s footmen gets in Surd’s way. Holmes flags down a passing cab, which proves to be carrying the Doctor; he claims to be following something which has been following Holmes and Watson, but all Watson can see out of the window are glimpses of the same sack on stilts he saw at Mrs Prendersley’s. They are overtaken by another hansom cab, and the Doctor loses sight of his quarry near the Library of St John the Beheaded. He, Holmes and Watson enter the Library to find that they are expected; Mycroft is here, and has taken it upon himself to contact another name on the list… the eldest Holmes brother, Sherringford.

Sherringford informs the others that some of the stolen books were the journals of their father Siger. The Doctor claims to have met Siger while travelling in India with his grand-daughter Susan, and further claims that the journals contained tales of Siger’s time in the East India Company, and a description of a hidden temple where the fakirs could chant open a gateway to another world. Intrigued by Siger’s tales, the Doctor arranged for his journals to be confiscated and placed in the Library, where he could consult them later when he had the chance. However, it appears that Maupertuis has stumbled across them, and plans to lead an army through the gateway and conquer the planet beyond in the name of Britain. Mycroft is openly skeptical until the Doctor tears aside a tapestry to reveal Sherringford’s other guest -- the sack on stilts, an alien being named K’tcar’ch from the planet Ry’leh.

Sherringford admits that he investigated his father’s tales some time ago, travelled through the gateway, and made contact with K’tcar’ch’s people. They are a peaceful race threatened by Maupertuis’ colonial ambitions; he has been raising an army from the criminal underclasses of London, and he intends to invade the Plain of Leng on Ry’leh. Siger’s journals contain the alien syllables with which it is possible to chant open the rift that connects the two planets; Mrs Prendersley was killed by Surd to prevent her from revealing those syllables to the Doctor. Maupertuis has now fled the country following the fight at the brothel, and is on his way to India to lead the invasion of Ry’leh. Holmes, however, reveals that he stole a book from Maupertuis as they struggled in the brothel, and he finds it to be one of his father’s journals. He and Watson agree to help the Doctor stop the invasion, and Mycroft, while unwilling to commit the British government to any course of action, nevertheless informs them that they may find assistance from a big game expedition in India which has been funded by the Diogenes.

The Doctor, Holmes and Watson take the SS Matilda Briggs to Bombay, where the Doctor’s friend Benny is waiting, disguised as a man to avoid attention. She tells them that crates labelled with Maupertuis’ handwriting were recently sent to the railway station at Jahalbahad, and the Doctor decides to follow them. That night, however, while perusing Siger’s journals he is attacked by a rakshassa, a flying demon with spikes for a face and bat-like wings. The rakshassa kidnaps the Doctor, leaving Benny, Holmes and Watson with no option but to continue on to Jahalbahad and continue their investigation alone. Colonel Warburton, the local Resident, invites them to a dinner with the Nazir Tir Ram, which is also attended by the hunter Lord John Roxton and a missionary named O’Connor. Watson excuses himself to answer a call of nature, but on his way back to the others he is attacked by Maupertuis and Surd, and barely escapes with his life. Benny also manages to escape, but the others -- apart from Tir Ram, Warburton and his wife, who are also involved in the conspiracy -- are taken prisoner.

Benny and Watson follow the prisoners to an underground temple, where the Doctor is being held as well. Maupertuis’ army is preparing to storm through the gateway and bring fame and fortune to Tir Ram’s formerly insignificant province, and Maupertuis can’t understand why his enemies oppose this. Roxton reveals himself to be a member of the Diogenes Club, and announces that Maupertuis is acting without the approval of the British government; however, Maupertuis feels certain that he will be rewarded when he presents Victoria with a whole new territory for her empire. He scoffs at the Doctor’s and Holmes’ claims to champion the defenceless -- and is even more scornful when O’Connor reveals himself to be the criminal mastermind Moriarty, here to find out why his underlings have been disappearing. Maupertuis summons four rakshassi to deal with the intruders while Tir Ram’s fakirs chant open the rift, and Benny and Watson join the fight, assuming that the rakshassi are trained animals from Ry’leh. Their intervention turns the tide, and Roxton shoots Surd before he can kill Watson -- but by the time the rakshassi have been killed, the army has passed through the rift, and it has closed up behind them.

The Doctor and Benny study Surd’s body and find that his deformities were caused by horrific vivisectional surgery which has all but hollowed him out. The books were smuggled out of the Library within the hollow spaces of his body, and his pyrokinetic powers developed due to the damage to his brain. The battle must now be taken to Ry’leh, and Moriarty, who is perfectly willing to let Holmes get himself killed on an alien world, departs after giving them a transcript of the fakirs’ chant. Holmes sends Roxton to report the situation to the Diogenes Club, and he, the Doctor, Benny and Watson chant open the gateway and pass through to Ry’leh.

Ry’leh is a barren world surrounded by a solid shell of frozen atmosphere. In this territory, Watson is in his element, tracking Maupertuis’ army through unknown terrain. Holmes, however, relies upon a comprehensive knowledge of his surroundings to make his deductions, and in an alien environment he is completely at a loss. The Doctor, meanwhile, fears that the fakirs’ chant mentioned the name of Azathoth, one of the legendary Great Old Ones, beings of unimaginable power who survived the destruction of the Universe which existed before this one. He has fought them before; amongst others, he’s encountered Yog-Sothoth in Tibet and London, Lloigor on Vortis, Cthulhu in Haiti, and Hastur the Unspeakable, who also goes by the name of Fenric. If one of the Great Old Ones is present on Ry’leh, the situation is even worse than he had imagined.

Watson locates Maupertuis’ army, but spots movement on the surrounding slopes as well, and realises that the ostensibly peaceful natives are gathering -- and are heavily armed. He tries to learn more by infiltrating Maupertuis’ camp, only to stumble into an ambush when the natives open fire. The panic-stricken humans scatter in terror, and Warburton blames Maupertuis; he was given no time to train the men properly, and it is now clear that he was misled about the strength of the native resistance. The furious Maupertuis shoots Warburton, but before he can do the same to Watson, the Doctor’s friend Ace arrives and shoots Maupertuis instead.

Ace has been on Ry’leh for some time, scouting out the situation for the Doctor, and she accompanies Watson back to the others’ camp to report -- only to find that they have been kidnapped. To Watson’s surprise, Ace reveals that the rakshassi are not animals at all, but an intelligent life form which worships a god living in a nearby city. She has seen them trying to sing open the rift to Earth themselves, and once chased one of the planet’s reptilian, three-legged animals through the rift to see what would happen. Leaving the battle behind, Watson and Ace climb a nearby mountain, using the swollen skins of balloon-like animals as suits to protect themselves from the cold and lack of air. Eventually they reach the summit, where they find a passageway carved through the ice onto the frozen surface of Ry’leh’s atmospheric shell.

The rakshassi have kidnapped not only the Doctor, Benny and Holmes, but Tir Ram and his fakirs as well. They are taken to the surface of the shell, where the rakshassi have transported a caravan across the top of the ice to avoid detection. There, the hooded figure, Maupertuis’ ally, is waiting for them -- and is revealed to be Sherringford Holmes. When Sherringford made his first trip to Ry’leh he met Azathoth, goddess of the rakshassi, and was converted to her cause. As the horrified Sherlock watches, Sherringford casts off the last vestiges of his human form and transforms into a rakshassi, as K’tcar’ch had done before him. K’tcar’ch’s people are in fact the Shlangii, mercenaries under orders to confine Azathoth to her prison on Ry’leh following her attempt to spread her Word across the Universe. Over the years, Azathoth has managed to convert a number of the Shlangii to her cause, but the rakshassi cannot sing the frequencies required to open the rift between Ry’leh and Earth. Maupertuis’ invasion was never meant to succeed; his army is merely here to keep the local Shlangii garrison occupied while Tir Ram’s fakirs sing open the gateway. Soon Azathoth will escape her prison of centuries, and bring her Word to the Earth.

Sherringford takes his prisoners to the central cavern to meet Azathoth herself, and the Doctor is somewhat disappointed to find that she’s nothing more than a giant telepathic slug, an empathic mutant playing upon the reputation of a Great Old One to convince her followers that she is a god. Ace and Watson are already here, and as they are apparently transforming into rakshassi themselves, Sherringford leaves them to guard the others; however, Ace and Watson are merely disguised, using hollowed-out crustacean body parts they took from the converted Tir Ram after Ace killed him. She is holding Azathoth hostage with a pre-programmed smart bomb, to ensure that it does not attempt to convert them to rakshassi; presumably the rakshassi are the adult form of Azathoth’s race, a stage which this mutant larva never reached.

As the Doctor ponders his next move, the rakshassi blast a hole thorugh the ice and lower the caravan through to the Plain of Leng, where Maupertuis’ army and the Shlangii garrison have wiped each other out. Azathoth manages to convert the smart bomb to her cause, but the Doctor and his friends survive its attack and flee. As the fakirs begin to sing open the rift, however, Ace reveals that she overheard part of Azathoth’s conversation with Sherringford during the séance, and has learned that a dissonant chord could shift the terminus of the gateway. After some thought and calculation, the Doctor works out a new chant which will shift the gateway to San Francisco during the earthquake of 1906. He and his friends join in the fakirs’ chant, moving the gateway to the Palace Hotel in San Francisco. Azathoth and her followers are forced to pass through the gateway when Shlangii reinforcements arrive, and the Doctor and his friends follow them. The rift closes behind them, leaving the immobile Azathoth trapped in the hotel as the fire raging through the earthquake-torn city consumes it. Sherringford attempts to kill Watson to avenge his goddess’ death, but Sherlock kills his brother to save his friend's life. They retreat from the hotel as it goes up in flames, incinerating every living thing inside.

The Doctor leaves the others, spends three months crossing America and the Atlantic Ocean, fetches the TARDIS from its resting place in London, and returns for his friends a moment after he left them. He offers Holmes and Watson the opportunity to travel with him, but they turn down his offer; one such adventure is enough for them. Instead, they return to 19th-century Baker Street, where Holmes resumes his career as a consulting detective. As usual, Watson writes up the adventure in his memoirs, and his friend Arthur Conan Doyle helps him to turn it into a novel; and, as usual, Watson and his friend’s names are changed to “James Watson” and “Sherlock Holmes” to protect their true identities. But unlike the other novels and stories on which Doyle has collaborated, Watson has done this one for his own benefit; the world is not ready for it, and The Strange Case of the All-Consuming Fire will never see print.