Beneath a deep blanket of snow, Jeremy Atiyah finds a sad region of China trying to emerge from its century of suffering

Beautiful but fragile, and probably destined to vanish at the first sign of spring. That's how she strikes me. When I first see Maomao she has frost on her Sophia Loren eyelashes. We are a thousand miles north of Peking, in a land of bitter winter, belching chimneys, blast-furnaces, throat-stinging air and rivers stiff with ice.

Beautiful but fragile, and probably destined to vanish at the first sign of spring. That's how she strikes me. When I first see Maomao she has frost on her Sophia Loren eyelashes. We are a thousand miles north of Peking, in a land of bitter winter, belching chimneys, blast-furnaces, throat-stinging air and rivers stiff with ice.

How can people enjoy themselves when they need to put on three pairs of trousers and a face-mask whenever they go out? "This is Manchuria, land of suffering," I want to say. "This is where I live," explains Maomao, before leading me to the scene of a giant ice festival on the river. I see children clutching live fireworks, red-cheeked girls posing for photographs, old men jumping into bobsleighs, toddlers eating toffeed fruits on sticks. On the Songhua River itself, so solid that it can take the weight of thousands, not to mention the occasional truck, we encounter horse-drawn sleighs, teams of huskies, and sellers of fireworks, silly hats, hot drinks and postcards. Behind a screen, fat women with painted lips dare to strip off and swim in a pool made of ice. And in the distance, I see miraculous structures built from translucent bricks: four-story towers, replicas of the Great Wall of China, Orthodox churches, laughing Buddhas, gigantic fruits and animals. I have finally reached Harbin, the last - and coldest - city in China.

What on earth am I doing here? Just clanking in on the train from Peking, I have spent one whole night watching Manchuria pass me by, jostling with men in black leather jackets in the restaurant car, slurping noodles and shouting for more beer. "Beneath this vast land lay countless sad lives," the Japanese artist Taeko Tomiyama wrote, viewing Manchuria from the same train, "...each of those lives, holding more suffering than can ever be told, was now just a clod of earth..." Between carriages, I found the windows feathered over with thick, opaque ice.

To be soaked in the cold blood of Chinese Communists, Japanese militarists and Russian industrialists: I worry that this may be Manchuria's only destiny. Last night in my compartment, three Chinese men lolled drunkenly together on the bed opposite mine. "You're Russian," slurred one. "What are you buying here?" From under the duvet I tried to imagine the original pristine wilderness of Manchuria, the prairie and the forest, a world of deer, wolves and tigers, populated by hunters, fishermen and ice princesses.

But now, when I eventually ask her about history, Maomao - an ice princess, of sorts - only smiles. What can she say? She is 20 years old, wears platform shoes, carries an ultra-slim mobile phone and inhabits the lobbies of Harbin hotels in the hope of bumping into Japanese tourists. Less than 400 years earlier, I would like to tell her, it was bands of tribal people from her homeland that rose up to challenge the might of the Ming court and its imperial capital Peking.

Instead, here by the banks of the frozen Songhua Jiang, I ask her if she is Chinese or Manchu, to which she responds by raising her watercolour- painted eyebrows. Does she care that in 1644 a Manchu boy named Shunzhi entered the Forbidden City and claimed the mandate of heaven to rule China? Or that China was then ruled by foreigners from Manchuria for nearly 300 years?

Probably not. She has aging parents to care for, and Japanese classes to attend, and warm clothes to buy. But this China of the Manchus - of men who shaved their foreheads and wore their hair in long braids at the back - is the China I have in my head, the China trespassed over a century ago by Russians from the north, driving their trans-Siberian railway to Vladivostok, then invaded by Japanese from the south.

I saw it all last night, sitting wide-eyed, watching this land of dirty snow, steam columns and freezing rail-lines slip past under yellow station lights. First stop was the city of Shenyang, which I had visited 11 years before - also in the dead of winter - in the days before the ice floes of Chairman Mao's China had begun to thaw. That time I had gone hungry, shuffling round Dickensian streets in a green Chinese army great-coat, choking on sulphurous air, slipping on iron staircases. That had been Chinese Communism, and it had smelt of rotten cabbage - but fear and loathing was nothing new to Shenyang. It was here, on 18 September 1931, that a group of Japanese army officers had set off explosives on a stretch of railway line, providing themselves with the excuse for a full-scale attack and the occupation of Shenyang - by Chinese reckoning, this is the true beginning of the Second World War.

Had that been the worst of Manchuria? Not quite. Hours later, my fellow passengers were snoring like trucks. And outside, there came creaking into view the city of Changchun. Xinjing, the Japanese called it, or "new capital". Here, on a bitter day in March 1934, Puyi, the last emperor of China, donned his dragon robes for a grotesque enthronement ceremony granting him lordship over the Japanese puppet state of Manchukuo. I remembered only what Puyi himself witnessed from a train window 11 years later: "Crowds of Japanese women and children, screaming and shouting," he wrote during his own attempt to flee the Communists in 1945, "were pushing towards the train as they wept and begged the gendarmes to let them pass. At one end of the platform the Japanese gendarmes and soldiers were brawling..."

I shiver, and try to sleep. Hours later, finally arriving in Harbin, the most northerly of China's great cities, I look up to see mounds of sooty, wind-blasted snow and the weakest of watery suns from the train window. The temperature hovers near -30C, but crowds of hatted people with steaming mouths stomp down staircases to the platform as we pull in; grand buildings emerge dimly through the freezing fog.

The Modern Hotel, where Maomao will stumble across me, is astoundingly ancient. The Russians built it in 1906, having put Harbin on the map courtesy of their trans-Siberian railway. Here I will breakfast every morning under vulgar gilt statues, chandeliers and plaster reliefs. In the streets immediately outside, I see signs on department stores and restaurants in Cyrillic letters as well as Chinese. Later I lunch with Maomao in a Russian restaurant where excellent bread is served and knives and forks are de rigeur.

If anyone should be unfortunate enough to settle in this skin-peeling Siberian wilderness, it will be the Russians, naturally. After the 1917 revolution, 100,000 of them came to live here in exile, building not only hotels and department stores, but Orthodox churches by the dozen. Small numbers of this old community still survive. I visit their domed cathedral, now full of trendy young Chinese inspecting a photographic display of Harbin's early days as a Russian railway outpost. I see languorous cabaret stars, Russian families picnicking by the Songhua Jiang, horse races, Model-T Ford motor cars, and six-storey skyscrapers. Postcards from the early 20th century describe Harbin as the "most civilised place in northern Manchuria".

Maomao, of course, cares little for all this. Nor does she see irony in her own fervent wish to reach Japan, despite the fact that 60 years ago her country was being colonised and brutalised by Japanese invaders. "Shall we go to KFC, or do you prefer Chinese hot-pot?" she asks, gently. The cobbled, pedestrianised streets of downtown Harbin are as pleasant as China gets, even under sheets of blackened, corrugated ice. She takes me underground, through endless bunkers, once built to defend Harbin against Russian missiles, now thriving clothes souks. Later we visit food markets where - in addition to winter cabbage - I am astounded to see summer mangoes and aubergines on sale.

The suffering is over, I tell myself. Surely. Even here in northern Manchuria. Maomao takes me to dinner where we eat jiaozi, steamed parcels of mincemeat wrapped in pastry, surrounded by tea-drinking families in padded coats. She is solicitous to refill my tea cup. She worries whether the grated potato and chilli salad is to my taste. Outside in the darkness, the temperature continues to drop, and the ice festival cranks into top gear. I hear firecrackers exploding. I say nothing, but it occurs to me that tomorrow I will be out of here. Maomao, on the other hand, will be wandering alone through these frozen streets, hoping to find her Japanese tourist, perhaps, before the arrival of spring.

Getting there

The writer flew courtesy of British Airways (tel: 0845 7222111), and his travel inside China was arranged through China specialists CTS Horizons (020-7836 9911). British Airways flies non-stop to (and from) Beijing four times weekly; flying time is around 10 hours. Return fares in February, after the Chinese New Year, are from £ 420 including taxes.

A three-night Beijing Package based on two sharing (single supplement £ 50) also costs £ 420 through CTS. Booking conditions apply. Valid until 25 March.

CTS can book travel between Beijing and Harbin by train or plane. The "soft sleeper" (ie first-class) return train journey would cost £ 106; travel time is about 14 hours each way. The return airfare from Beijing to Harbin is £ 163. CTS can also book transfers.

Where to stay in Harbin

The five-star Shangri La costs £ 59 per night with breakfast. The writer stayed at the three-star Modern Hotel, at £ 43 per night with breakfast.

Harbin sightseeing

You can book a personal city tour in Harbin (seven hours) with an English- speaking guide, taking in the ice carvings, the snow carvings, the Tiger Garden and Sofia church, for £ 69 for one person or £ 47pp for two to five people.