Klose's 34th-minute strike leaves Germany four points clear at the top of Group Four and means they cannot be caught by their main pool rivals Russia regardless of either side's remaining World Cup qualifier on Wednesday.
Russia play Azerbaijan in Baku while Germany host Finland in Hamburg in their last qualification game, but Guus Hiddink's Russian side now face two-legged play-off matches if they are to reach South Africa.
Hamburg defender Jerome Boateng started his first international in the cauldron of Moscow's Luzhniki Stadium, but a second yellow card midway through the second-half earned him a red card as Germany finished with ten men.
Russia made a strong start and missed the opportunity to take the lead after nine minutes when Alexander Kerzhakov got in behind the German defence, but the Dinamo Moscow forward volleyed wide.
Germany's best chance came when Mesut Özil made a strong run into the head of the defence and Lukas Podolski's shot was blocked by defender Vasili Berezutsky on 22 minutes.
German goalkeeper Rene Adler was the visitors' hero with at least four world-class saves and looks set to travel to Africa as the number one choice ahead of Hannover's Robert Enke.
Adler pulled off a superb save when Russia captain Andrei Arshavin slid a perfect pass through the German defence to Zenit St Peterburg midfielder Vladimir Bystrov. But Adler made a save with his legs from point-blank range and it proved to be crucial as Germany took the lead moments later when Klose netted.
Despite Russia's pressure, Germany got the breakthrough when Podolski's pass found Özil down the left side of the penalty area and Klose slipped his marker long enough to flick the ball past Igor Akinfeev.
After the break, Germany defender Philipp Lahm fired wide past Akinfeev, but Adler was Germany's saviour again with two world-class saves in quick succession as his defence did him few favours.
On 55 minutes Arshavin unleashed a fierce drive directly at Adler which the 24-year-old German did exceptionally well to block, before an acrobatic effort by Vladimir Bystrov landed on the roof of the net.
Boateng earned himself a second yellow card when he brought down Bystrov after 68 minutes on the edge of the penalty area to leave his country facing the last 20 minutes a man down.
Adler again came to Germany's rescue when he saved from Igor Semschov as Russia poured forward with time running out.
And Russia missed out on a penalty in the dying stages when replacement defender Arne Friedrich appeared to commit a foul in the box, but the referee waved play on.
After that, Joachim Löw's side safely saw out the game and leave Moscow with the three points.