As the Russians vote in a poll on a national television station to choose the greatest Russian, Stalin and Nicholas II jostle for the crown. This seems strange. Stalin killed 25 million and sent 28 million through his Gulag camps while, during his own disastrous reign, Nicholas II displayed brutal insensitivity and political ineptitude, faced two revolutions, lost two wars, his throne and his life.

In the BBC Great Britons poll, this game was won by Churchill. Charles I, our equivalent of Nicholas II, didn't appear; Henry VIII, the English Stalin, was No 40; Cromwell, our Lenin, was tenth but our heroes were more Eric Morecambe than Ivan the Terrible.

Two people would not be amazed by Stalin's popularity. The first? Vladimir Putin, now paramount leader of a motherland of imperial oil-rich swagger, recently introduced a new textbook to teachers that acclaimed Stalin as “the most successful Russian leader of the 20th century”, a cross between Peter the Great and Bismarck, who committed some “excesses” but became a great war-winning Russian ruler.

The second person would be Stalin himself, who studied history and promoted himself as a Russian emperor, musing that “Russians need a tsar”. He compared himself to Ivan the Terrible and Peter the Great. I have held a book from his library, a biography of Ivan, in which he wrote “teacher”. He said Ivan's mistake was to kill too few of his boyars.

Stalin foresaw that Russians would forgive his murders if they appreciated his reasons - to accelerate a socialistic paradise, defeat the Nazi invaders, create a superpower, win an empire. And this poll proves him right. Hence he told the movie director Eisenstein, who was making an Ivan biopic: “You need to explain why Ivan needed to be cruel.” Othertimes he told his henchmen the “great thing about the Soviet model of government is that we get things done fast - by shedding blood.” He is meant to have said: “One death is a tragedy; a million is a statistic.”

Until 1956, Stalin was worshipped. Khrushchev exposed his crimes (very selectively), inventing the idea, which gulled many Western leftist intellectuals, that Lenin's Soviet state was a noble, decent project distorted by a murderous psychopath. In 1991 Russians were humiliated by Soviet collapse, shocked by archival revelations of Soviet criminality. Lenin - third in the poll - was exposed as a frenzied killer and terror mastermind. The entire regime was built on mass killing.

Yet by 2000, when Mr Putin was elected president, the Russians were sick of humiliation, poverty and insecurity. Now they saw in Stalin a stern glory: he was a world conqueror who expanded the empire from Berlin to Ulan Bator, defeated Hitler, built and thought in imperial style and industrialised his country, leaving a nuclear superpower. To the West, he was a murderous monster, but without Stalinist Russia we would have lost the Second World War. Stalin appreciated this: when the US envoy Averell Harriman complimented him for taking Berlin, Stalin answered: “Yes, but AlexanderI made it to Paris.” Stalin loved running his pipe over his empire on maps: “Yes we haven't done badly...”

But he would have been bemused by the presence of Nicholas II - and so would Nicholas himself. If Stalin wins the poll, it's a crime; if Nicholas, a farce. Nicholas and Alexandra have won an absurdly good press because they had a loving marriage, an ill son, a tragic death. Nicholas is being canonised by the Orthodox Church.

But Nicholas was not romantically unlucky: he was a rigid autocrat, bigoted racist, clumsy warlord, an enthusiastic anti-Semite who sponsored, organised and financed the Black Hundreds and Cossacks in their pogroms that killed many thousands of Jewish women and children. Savage to those helpless victims, he was too lenient to revolutionaries. During both his disastrous wars - the Russo-Japanese and the First World War - he was callously inept. Alexandra was worse: foolish, hysterical, deluded, yet in the last years Nicholas allowed her far too much power. When they were in Bolshevik captivity, he and Alexandra read primitive anti-Semitic literature. A more capable Tsar would have avoided the tragedies of the Bolshevik terror.

In Russia, history is real and the blood is fresh: in the archives one can virtually smell it on the deathlists. The truth is a golden privilege; the past in Russia is still a secret place. The Russians have a Janus-like amnesiacal view of history: they acknowledge the killing as “mistakes” then they celebrate the triumph and magnificence of power.

Who would I choose? Among politicians? Catherine the Great and Potemkin. Soldiers? Suvorov and the ruthless Marshal Zhukov to represent the 27 million who died fighting Hitler. But to me, Russian greatness is about art, not empire - Tolstoy, Tchaikovsky, Babel, Pasternak. The astonishing genius that was Pushkin is my No 1, Russia's greatest hero.

Stalin and Nicholas are beloved for what they were not. Nicholas ironically symbolises sacred martyrdom of peasants and citizens under Bolshevism - no longer the bigoted, arrogant, bungling autocrat. Stalin is no longer the homicidal Georgian cobbler's son and fanatical Marxist tyrant, but the Red Tsar, the greatest Russian emperor of all. One day he will appear in the textbooks with Peter and Catherine as Stalin the Great.

Simon Sebag Montefiore is author of Young Stalin and Sashenka: a Novel of Love, Family, History and Redemption across 20th-Century Russia.

Times Recommends

• The ghost of Robin Cook haunts Chilcot’s feast
• The truth shouldn’t need oaths
• Violence: let’s separate the men from the boys