History is being put into reverse in St Petersburg. Or do I mean that it's being re-established? Near where the cruiser Aurora trained its guns on Kerensky's Provisional Government, a Neva-side road has again become the English Embankment. It had spent the Soviet decades as the 'Maklinsky Embankment'. Socialist Scots may grieve. The 'Maklin', thus honoured, was the Red Clydesider, John Maclean.

 

Church of the Spilled Blood As it reaches its 300th anniversary in May, the city has become a cryptic crossword. The British still speak of the 'Kirov' theatre and ballet, as they did during Valery Gergiev's triumphs last year at the Proms and the Barbican. But in St Petersburg they've ditched the crocodile-tears tribute to the Leningrad party boss whose killing Stalin ordered. It's the Mariinsky once more, in homage to Alexander III's tsarina, Maria Fedorovna.

Vladimir Nabokov would be happier with St Petersburg now, I think, as the communist nomenclature fades. I've brought his autobiography, Speak, Memory, with me. In one picture caption he mocks the Soviet re-labellings. Morskaya Street, where his family mansion stood, became Herzen Street. As unforgiving as ever, Nabokov notes that Herzen — hero of Tom Stoppard's recent trilogy — was "a famous liberal (whom this commemoration by a police state would hardly have gratified)." It's now back to Morskaya Street.

I take my morning walk past the permanently moored Aurora – a grey, pocket-sized three-master — after fighting across the ferocious commuter traffic. A policeman sits idly in a glass box beside the multitudinous Volkswagens and occasional Ladas. Ten years ago, the city had 150,000 private cars. About one and a half million now, and no money for a new traffic light system.

Yesterday a bride, all in white, was being photographed with the Aurora as backdrop. This goes on at all the city landmarks. At the equestrian statue of the city's founder, Peter the Great — Pushkin's 'Bronze Horseman' — which is just across the street from the central Wedding House (a glorified registry office), I saw one bride in bright scarlet, veil and all.

A young sailor hurrying to duty on the Aurora mimes with his fingers as if puffing a cigarette, and asks me if I can spare one. I bolt together some phrases in my painfully revived Russian and say I don't smoke. He tells me to go to Hell. The embankment here is like a Russian version of Seurat's La Grande Jatte, but in blues and greys. Five men are fishing over the granite river-wall. We're across the Neva from the heart of the city. The occasional flashes of sun reflect off the gilded domes of those cathedrals which aren't covered in scaffolding in preparation for the anniversary celebrations. Putin is a Petersburg man, and he's pouring federal funds in.

Gilt money. He wants the best possible face presented to the world — a classic obsession of Russian rulers. Workmen have re-paved Palace Square, in front of the Hermitage. Here's where all those faked-up revolutionaries stormed the Winter Palace in Eisenstein's film.

Emblems of tsarism are being restored; names put back; museums of atheism returned to ecclesiastical use. It's a reinvention of tradition. In a city struggling with deep poverty and administrative chaos, old symbols are again clung to. You have to believe in something.

Every other day I pick up a handful of mineral water bottles at a small, heavily guarded supermarket. Ever since John Snow discovered, in early 19th century London, that cholera is water-borne, pure water has been the basic public-health necessity. All those Africa charity ads proclaim the same message. Yet St Petersburg tap water is a curious brown, packed full of giardia, the classic Third World stomach-churner. It's 85 years since the October revolution, which supposedly changed everything. I notice that Petersburgers now call this Russia's 'third revolution': last in the queue after 1905 and February 1917. None of the three produced clean water. Hostile critics spoke of the Soviet Union as 'Upper Volta with rockets'. With palaces as well, to be fair.

For all its beauty, St Petersburg and its canals remind me of Amsterdam, more than Venice. It's partly to do with the northern light.

But it's partly because even the palaces, despite their profusion of caryatids (female) and atlantides (male) holding up the balconies outside, don't have the Renaissance elegance or baroque frenzy of the Venetian equivalents.

Some are similar to what 19th century American robber barons built. There's even a touch of Potsdam, the Hohenzollerns' garrison town. St Petersburg was always an ultra-military city, built with forced labour, from Peter the Great's time on. Those who disliked it called it 'the city of bones'.

It's hard to find anyone smiling in St Petersburg, even allowing for the usual unfriendliness of city-dwellers. I decide it must be the long hangover of the years when it was risky to be friendly with strangers. Sally, my wife, conducts a campaign to try to tempt museum attendants — the grimmest people in any city — into a smile. Her top score is five, in the Hermitage.

The camera always lies. What photographs don't communicate is the sheer scale of St Petersburg: the width of the river and the canals, the vastness of the palaces, the enormous length of avenues like Nevsky Prospekt. The idea was to out-Versailles Versailles or out-Rome Rome. But I remember the sharp, rather camp criticisms by the Marquis de Custine, who's the nearest equivalent, for Russia, of Tocqueville on America. Writing in 1843, this renegade son of a guillotined father noted the Russian obsession with facades : with how a thing looked, rather than how it worked. He asserted that this was true of government, not only architecture.

Apparently, Peter the Great issued a decree that all previous decrees should be carried out. Is it any different for Putin?

One evening, with two friends, we walk on beyond St Isaac Square to visit the cathedral of St Nicholas. This takes us past the Yusupov palace, where Rasputin was killed by his courtier rivals. It's too near to closing time for us to buy a ticket. But I go down to the cellar, to the gents. The cellar is where the murderers began trying to kill their man.

There's a Rasputin Bar. From the gents, I go back up the stairs, feeling that I've been vaguely in touch with history.

The Nicholas cathedral is, I suppose, the heart of Christianity in the city. While city centre churches, such as the Kazan cathedral, became museums of atheism, this was left alone. Like London's Windmill theatre, it never closed, even during the siege. It has an 18th century delicacy many St Petersburg monuments lack. There are, as always, the five symbolic domes (Christ above the four apostles), and a slender golden spire. The walls are pale blue and white, like porcelain.

Walking along these streets is like dipping back into Dostoevsky. The high 19th century tenement blocks have open, arched entrances. Everything is desperately shabby and run-down, even though the Mariinsky and the Conservatoire are just down the way. A semi-tsarist economy seems to have returned, with the greatest efforts going into the palaces. Putin is burnishing up a summer residence for himself outside the city.

People are visibly up against it, unless they're in the parallel dollar-economy. Big houses for the 'New Russians' are being built in the old royal villages of Tsarskoe Celo and Pavlovsk. St Petersburg jokes : A New Russian brings his Mercedes to the dealer's for trade-in. "But, Mitya, you've only had it a week." "I know, but the clock stopped." Another New Russian buys a VW Golf. "But, Vanya, why is a man like you buying such a small car?" "How else can I get down the corridors in my new house?"

The murder in Crime and Punishment is supposed to be set not far from the Nicholas cathedral. Perhaps wimpishly, I suggest to Sally that she fastens her raincoat collar over a heavy silver chain. It suddenly seems to glint all too appealingly. Dostoevsky's great-grandson is a St Petersburg tram-driver, I'm told, with the family passion for gambling.

Mothers and children play in the cathedral gardens. When we turn into the entrance, a little line of women begging moves towards us. Everyone looks old or weary, or both. These are the people who've lost the security of the so-called 'Years of Stagnation', overseen by Brezhnev – no pensions, no wages. Ivan Karamazov's Grand Inquisitor said: give people bread and they'd willingly give up their freedom. I suspect that all these would.

The woman at the desk, selling thin yellow candles, says the service starts at six, in the crypt. We move inside. It is dark, apart from the glitter of icons and the lights in front of the iconostasis. St Nicholas is in a heavy silver frame, but supplementary icons line every wall. A woman in a grey smock goes round polishing each glass cover after it's been kissed.

We sit on a green-painted chest to watch and wait. An old woman sitting next to us is here, I think, to keep warm. A young man, with a heavy black beard, stands by one stone pillar, hardly moving all the time we are here: another Dostoyevsky image. This is not the usual gathering of the elderly you expect to find in western European churches. Young women with babies, a man on his way from the office with his briefcase, people of all ages.

While we wait, I go out to see if a bus runs near-by that we could use to get back to our hotel. The No. 3 sounds plausible, to judge by the placard at the stop. I try to confirm this with a passer-by. He thinks it will be all right, but he regrets he's not local. I turn and ask a huge women with a shopping bag. She thinks the No. 3 is a bad bet. The two of them start to argue ferociously. I think they are about to start a fight over the right advice. After a few minutes, I wave my arms appreciatively and slip back for the service.

The singing is beautiful beyond words. I think at first that it must be a tape, the music is so loud and clear. But by going along past a pillar, I can see it is six young singers. We find out afterwards that they come from the Mariinsky. Somehow, the curve of the roof above them amplifies their voices. We are all – one atheist (me), one Jew, one Anglican and one part-time Anglican — deeply moved.

From the Evelyn Waugh letters, I remember his comment to Orwell, who'd sent him a copy of Nineteen-Eighty-Four, that, though he enjoyed the book, he thought Orwell was wrong to omit any reference to religion. This, he was sure, would outlast any political system, however oppressive. At the time, I thought that this was just Waugh being reactionary, but undeniably he was right.

The Romanovs have become a cult in contemporary St Petersburg. People hold up their photographs at public gatherings. The murdered Nicholas II and his family have been re-buried in St Petersburg, in the Peter and Paul cathedral. The Orthodox hierarchy have declared them all to be saints.

But, for some reason, the churchmen don't wholly believe the scientists' DNA tests on the bones. (They may worry what tests on other sacred bones might reveal.) So it's not yet full-scale Romanov worship, complete with icons in front of these new tombs. I'd bet it soon will be.

One corridor, leading out of the echoing cathedral, is lined with photographs of Romanovs who are still alive, in various bits of the west: Paris, Florida, California, Berlin. There are rows and rows of them, mostly with the same beaky nose and a well-groomed, cosmopolitan, upper middle class air. I see that Princess Julia Romanov, photographed in her tiara, lives in Sydney. I wonder what they make of her there.