In the late 1930s the Scottish adventurer Fitzroy Maclean reached the ‘ice-blue peaks’ of the Tien Shan range at the fringe of the Soviet Union. Beyond lay a land whose very name breathed romantic allure. ‘Chinese Turkestan,’ wrote Maclean, ‘temptingly near and temptingly inaccessible.’

Remote and unknown to most westerners, it was, however, of keen interest to Stalin. His police spies trailed Maclean, a young diplomat at the British Embassy in Moscow, who was on a whimsical Great Game of his own to explore Central Asia.

Maclean got as far as the border, where he turned back in the face of a terrified refusal by the Chinese to let him in. The Chinese consul hid, his underlings wrung their hands and the Soviet NKVD escorted the unwelcome visitor onto the first train out. And that was that.

Russia and China are not friends. The two Asian giants tangled for centuries over the vastness of resource-rich desert and mountain between them. They remain uneasy neighbours. Their leaders, Xi Jinping and Vladimir Putin, recently proclaimed a partnership in a ‘new order’. But they are trapped by geography, birth rates and strategy in a very old order; one that explains why the Chinese leadership distrusts the Kremlin, fears its own subjects and keeps an iron grip on the borderlands.

‘Chinese Turkestan’ only exists in vintage travel books. Today it is officially known as the Xinjiang Uighur Autonomous Region. It is in the news because China is accused of committing crimes against humanity in a campaign to instil what it calls ‘stability and order’ among the original inhabitants and Chinese settlers, who now outnumber them.

The Communist regime’s well-documented abuses against the Uighurs, a Turkic Muslim people, are so gross that they tend to obscure a paranoid insecurity that is as real today as in a bygone age when nervous functionaries sent Fitzroy Maclean packing.

Most outsiders do not know that on three occasions – in 1934, 1937 and 1945 – the Soviet Union seized control of parts of Xinjiang, while Muslim separatists twice declared independence.  Nor are they aware that as late as the year 2000, groups based in Kazakhstan, the successor state to the Kazakh Soviet Republic, were waging an armed struggle against China.

The Chinese government has assuredly not forgotten. When it was weak, China’s existential fear was neither militant Islam nor the oft-proclaimed foreign ‘plots’ to divide the country. It was the presence of the Soviet Union, a big nuclear weapons power, on its border, at intervals hostile or comradely depending on the despots of the day. That has not changed.

The name Xinjiang means ‘new frontier.’ Even this is nothing new. It was christened thus in 1884 when the late Chinese Empire made diverse areas into one province to reinforce its authority while Tsarist Russia marched into Central Asia.

The Chinese claim has been dated to the first century AD, when the Emperor Wu Ti, fifth ruler of the Western Han dynasty, sent soldiers into the region. It was not until the eighteenth century that the emperors of China’s last dynasty, the Manchu Qing, gained control with the capture of Kashgar, in the far west.

The eminent Harvard historian of the period, Joseph Fletcher, wrote that the Qing tried to segregate the few Han Chinese colonists and practised ‘non-interference’ in local Muslim affairs. They still had to put down successive revolts with the sword, leading Fletcher to conclude that in the nineteenth century Xinjiang was ‘the most rebellious territory’ of the realm.

In the south, most people were Uighurs. In the north, Kirghiz, Russians, Kazakhs, Tajiks and Uzbeks mingled with Han Chinese migrants. A third significant community was composed of Chinese Hui Muslims, also known as Tungans, who had Asiatic features, practised a mild form of Islam and were often at odds with the Uighurs. They were scattered across Xinjiang.

In short, there were two regions, a mix of peoples and prolific religious, territorial and national conflicts. It was ripe for Russian exploitation. Nor did tension ebb when the Tsarist conquests reached their limits.

By the mid-twentieth century both Russian and Chinese empires had expired. Their successors struggled to control swathes of territory. The Bolsheviks aimed to secure the borders of their new state. In far-off Nanjing, the Nationalist regime of Chiang Kai-shek, the Kuomintang, tried to hold China together.  Khans, emirs, Sufi divines, bandits and warlords occupied the ungoverned spaces between the rivals.

From the fall of the Manchus in 1912 to the ascent of Stalin in the early 1930s the politics of Xinjiang dissolved into fiefdoms of rebels and mystics, areas under the nominal control of the Nanjing regime and a healthy dose of Bolshevik intrigue. Xinjiang was a minor theatre compared to the front against Imperial Japan but it was a place where complex ambitions clashed.

One of the few detailed studies of the period, Warlords and Muslims in Chinese Central Asia, by Andrew Forbes (Cambridge University Press, 1986), argued that most historical accounts focused on great power rivalries, overlooking the rise of political Islam and the place of Xinjiang in the wider Muslim world.

In the light of today’s conflict, whose roots are racial and religious, that assessment stands the test of time. But to grasp why Xinjiang is fundamental to Chinese thinking on security, one needs to look at how it was almost torn away from the central state.

In 1933, a group of rebellious Muslim leaders proclaimed the establishment of a ‘Turkish-Islamic Republic of Eastern Turkestan’. It was based around the oasis town of Khotan, a far-flung outpost along the trade route winding south of the great Taklamakan Desert.

Their programme was radical. The republic was to be governed by Sharia law, accompanied by social and economic reforms. It was anti-Han Chinese and opposed to the Hui Muslims. The divines set up the apparatus of government, with a cabinet, a national assembly and a flag showing a white star and crescent on a light blue background.

It was telling, however, that their key platform was to resist Soviet penetration of the region and to defeat atheistic Communism. Evidently the founders thought this would win them international support.

Emissaries from the new ‘republic’ set out for British India, its authorities dispatched a telegram to the Turkish government conveying greetings from ‘liberated Eastern Turkestan’ and envoys went to Kabul to seek arms and recognition from the kingdom of Afghanistan.

All these efforts failed. The British rebuffed the overtures, saying that they recognised Chinese sovereignty. Turkey, which was in the throes of secularisation under Mustafa Kemal (Ataturk), did not want an engagement which might start another war with Russia. The Afghans received their visitors courteously and sold them a small amount of arms but did not extend formal recognition.

As Forbes remarks, the attempt to set up a secessionist state ‘was doomed from the moment of its inception’. The uncompromising ‘Turkic-Islamic’ stance won no friends and put the rebels at odds with the three most powerful elements in Xinjiang – the military forces of the Hui Muslims, the Chinese regime and the Soviet Union.

It was Soviet intervention which proved decisive. Stalin saw turbulence in Xinjiang as a threat. It raised the risk that Britain, Japan or Germany would sow trouble on his southern flank. The Politburo was already concerned by intrigues in Tibet, publicly denouncing any thought of a ‘Greater Tibetan Empire.’ As the chaos intensified, Moscow responded with alacrity to an appeal for help from its warlord friends.

In late 1933 a seasoned Soviet emissary was sent to Urumchi, the region’s capital. A prompt purge of the local security forces followed. Twenty White Russian officers were shot. The main warlord, Sheng Shih-tsai, obediently announced a political and economic programme aligned with the Soviet Union and became, in effect, Stalin’s puppet.

Soviet units entered Xinjiang in January 1934. The Russians ignored the Chinese government at Nanjing and sent in tanks, artillery and aircraft to accompany two crack regiments of state security troops. They fought everyone in sight, defeating rival warlord forces with the use of poison gas, according to Peter Fleming of The Times, who covered the small war. Its latter stages became extremely complex: suffice to say that in the whirlwind the nascent ‘Turkic-Islamic Republic’ collapsed.

Three years later, Stalin intervened again. This time it was to tighten control over his satraps, who had failed to stop a sequence of bloody uprisings. In one, rebels executed all the local officials they suspected of Soviet sympathies. They laid siege to the symbolic far west city of Kashgar, at the gates to the Hindu Kush. Once more, Soviet political capital and economic investments were under threat.

In May 1937, responding to an ‘invitation’ from his puppet, the Soviet leader ordered tanks and infantry into action with air support from bases in Soviet Central Asia. The Red Army made short work of its foes, a rabble of disparate forces. For the first time, the Kremlin stationed a garrison in the south of Xinjiang to buttress its conquests. Soviet prospectors began to extract oil and minerals – including uranium –  while commissars bullied their Chinese counterparts into mining concessions.

None the less, Stalin’s diplomacy was sophisticated. He saw how the Axis powers were aligning and decided to boost the Chinese nationalists against Japan. Within months of the second Soviet intervention, a Sino-Soviet Non-Aggression Pact was signed and munitions began to flow to Chiang Kai-shek’s forces. The NKVD conducted a classic purge of hitherto unsuspected ‘Trotskyists’ inside the Xinjiang administration; the ‘conspirators’ either vanished into the Soviet Union or were executed. While world attention was elsewhere, the far west of China had become a Soviet satellite state.

Throughout the Second World War, the Russians held on to their power. But by its end, the sands were shifting again. The Chinese Communists under Mao Zedong emerged dominant after the defeat of Japan. The Kuomintang nationalist government began to disintegrate. While the United States and the Soviet Union vied for influence, Stalin’s lack of scruple proved decisive.

In August 1945, a new Sino-Soviet Treaty of Friendship was signed in Moscow by the Kuomintang’s representatives. At the same time, their Soviet hosts were playing a double game. Once more, Xinjiang was rent by uprisings by Kazakhs, Muslims and sundry armed minorities. Atrocities multiplied: one account spoke of Kuomintang forces shooting hundreds of people in batches, then dumping them in mass graves. Out of the mayhem came a shadowy group first established clandestinely in 1944: the East Turkestan Republic, or ETR.

Its stated programme was a secularised ‘democratic base’ for reform and progress, allowing religious freedom while emphasising ‘friendly relations’ with all powers, ‘in particular’ with the Soviet Union. The leaders vowed an end to ‘slave life under the yoke of the Han’ and raised the ‘revolutionary flag of the crescent and star… the blood debt has not yet been paid by the Han Chinese.’ Rhetoric apart, it was like other Soviet front organisations of the time.

‘It is now possible to state with certainty that the Soviet Union was deeply involved in the establishment of the ETR,’ concluded Forbes in his work on the period. The ETR became strong enough to compel the Chinese authorities to recognise it in a political settlement.

But Stalin and Mao had not done with intrigue. The Chinese civil war ended with the defeat of the Kuomintang and the collapse of its authority in Xinjiang. With its fall came the eclipse of the East Turkestan Republic, which had outlived its usefulness. Mao’s Red Army reached the cities of the far west and seized control of the region while the Russians withdrew. The two tyrants began a period of Sino-Soviet ‘comradeship’.

In December 1949 a cryptic communique from Beijing disclosed that the key leaders of the ETR had been killed in an unexplained plane crash in Manchuria in August that year while on their way to talks in the capital. The four-month delay in announcing the crash was also never explained. With their demise, ‘East Turkestan’ vanished from history.

Over the next five decades, China developed Xinjiang, laced it with roads and railways, built cities and tested atomic bombs in the desert wastes. The economy was run by a huge military corporation, like a parallel state. There was a mass influx of settlers. ‘The Chinese have made the Uighurs like pandas, a species on the edge of extinction,’ said an exiled leader, Isa Yusuf Alptekin. One statistic said it all: in the late Republican period Han Chinese accounted for between three and four percent of the Xinjiang population. By the year 2000 they were a majority.

At the turn of the century, I found a ghost of the lost nation in Almaty, the capital of independent Kazakhstan. ‘Agha’, or the ‘revered one,’ Yusufbeg Muhlisi, was eighty years old. He lived in a crumbling Khruschev-era apartment block, poring over maps amid flags, photographs and mementos of the state. From time to time his telephone rang with news from ‘occupied Turkestan’. A former officer in its army, Muhlisi was the leader of the ‘East Turkestan Liberation Front’. He was running an insurgency.

For years, rumours in China spoke of mysterious explosions and deaths across Xinjiang. They appeared to occur with regularity. In 1997 I visited Kashgar for the Sunday Times, awakening one morning to find the streets full of armoured vehicles and steel-helmeted troops. It was impossible to print an eyewitness account without endangering our local contacts, so the newspaper made the responsible decision to withhold publication while we pursued inquiries. They led across the Tien Shan mountains to the lair of the ‘Agha’.

Chinese censors could not make up their minds how to handle the insurgency. At first, alert readers noticed a proliferation of news reports about exploding domestic gas canisters and inexplicable traffic accidents. The silence broke in the summer of 2000, when an official newspaper, the Talimu Daily, said that in one region, Aksu, the police ‘destroyed 78 violent terrorist groups, captured 768 suspects, caught 153 violent terrorists and cracked 633 criminal cases’. They also seized 908 illegal guns and some 3,000 kilos of explosives from ‘separatists and extremist religious elements’.

On July 10, 2000, another official paper, the Xinjiang Legal Journal, lionised a Chinese officer, Long Fei, who was shot dead, aged 29, as he tried to arrest ‘seven terrorists of the Islamic Allah Group’. The recipient of seven gallantry awards, he killed two of the ‘terrorists’ before being fatally wounded in the neck.

The same paper printed a gruesome account of the death of one Hudabaidi Toihuti, a Uighur, whose ‘firm stance’ in support of China brought assassins to his door. They stabbed him 34 times, then dispatched his son with a gunshot.

On 17 November 2000, a legendary rebel known as ‘Shakhniaz’ led a group of fighters out of the Taklamakan Desert to hurl grenades at buses carrying Chinese migrants along the Silk Road. Dozens were killed. He was reputed to plan a strike every Friday, the Islamic holy day, and to leave a defiant message at the scene of every attack.

A few weeks later I put these reports to the elderly ‘Agha,’ who was unmoved. ‘This is not terrorism but a fight for national liberation,’ he said. ‘It’s like Bosnia or Chechnya. What’s different is that for our people time is running out.’

Then I went out of Almaty over snowy roads to a farmhouse, where Muhlisi’s deputy, Abdrazak Imam, had his base. His first piece of news was sobering. A young Uighur, who had acted as a guide for a BBC documentary team, had been arrested and shot by firing squad, he said. The Sunday Times made every effort to confirm the story from the official Chinese media, without success, and, once again, took the responsible decision not to publish it. I have no doubt it was true. But it showed the problems of establishing facts in Xinjiang.

In late 2000, a think tank, the China and Russia Institute, which advised the Kazakh government, described Muhlisi’s ‘Liberation Front’ as ‘a typical extremist organisation’, which had been passive until it revived in 1990. It had some 90 training bases, funded itself with bank robberies and staged more and more bombings and gun attacks against the Chinese.

All that ended after September 11, 2001, when China joined the ‘global war on terror’, the US and its allies invaded Afghanistan, and the Kazakh government, like others, moved to shut down ‘sanctuaries’ for armed groups. Cross-border insurgency ceased. The Uighur militants faded into obscurity; if Muhlisi survived he would be 103 years old today.

The way was clear for successive Chinese leaders to turn the screw. Overtly colonial policies in Xinjiang set off waves of ethnic violence and random acts of terror by the Uighur resistance. In 2009 racial riots convulsed Urumchi: it was still possible to find out facts by tramping up through the snows to count the fresh graves of young men in the Muslim cemetery, but the space for independent reporting soon vanished.

Xinjiang today lives under the heaviest surveillance in the world; its troublemakers put in re-education camps, its young men exploited as labour, its Muslim women subject to forced sterilisation and its society stifled under a cloak of ‘harmony’. The toll of crimes against humanity is certain to rise as more documentation is sneaked out. It is a hidden tragedy. Could it have been different?

In the 1950s, the Communists realised that enforcing radical land reform and collectivisation in Xinjiang was a route to perpetual conflict. Mass arrests and repression were merely fuelling ethnic resentment. The party changed tack. The minorities were tolerated, religion permitted under control and collaborators were brought into local government. In short, China copied the Soviet Union’s model of rule in Central Asia. The man behind the change was Xi Zhongxun, the father of today’s leader, Xi Jinping.

This compact endured for decades until it broke down under the pressures of population growth, economic change and social disruption in China, accompanied by the contemporary surge in radical Islamic politics, the Soviet retreat from Kabul and the victory of the Afghan mujaheddin. It is not clear what lit the spark of violence in Xinjiang but by the time I found the ‘Agha’ in exile, the fires were burning. They have not yet gone out.