The midnight plane to Georgia now takes off three times a week. Starting last Wednesday, British Airways has added to its schedule an overnight flight from Heathrow to Stalin's homeland.
The six-hour journey to the capital, Tbilisi, is aimed squarely at business travellers, who are charged £2,500 return to reach the turbulent Caucasus. But the back of the plane could soon be filled with British holidaymakers, paying just £400 for a return trip to the scene of the 2003 "rose revolution", a country described by John Steinbeck as one of the most beautiful in the world.
Traditionally, the nations of the former Soviet bloc have entered British consciousness only in the opening stages of European football competitions, when the likes of Manchester United, Arsenal and Liverpool are drawn against teams known generically as "FC Unpronounceable".
Yet this summer, hundreds of thousands of British holidaymakers are moving east, shifting allegiance from the Mediterranean to the Black Sea.
Most are aiming for Bulgaria, where the number of British visitors increased by two-thirds last year. Others will head for the empty beaches and cultural treasures of Romania and northern Turkey. But some will be more adventurous, because, suddenly, access to two former Soviet republics, Ukraine and Georgia, has become much easier.
Yesterday, the US, the traditional summer destination for millions of British travellers, tightened its immigration rules still further: children are no longer allowed to travel on a parent's passport, and anyone without a "machine-readable passport" has to apply for a visa.
But as American red tape gets ever more tangled, parts of the former USSR are throwing open their frontiers to attract visitors. Last month, Ukraine scrapped the arcane bureaucracy that has thwarted many a prospective visitor. Before, only tourists with deep reserves of time and patience were prepared to undergo the complex and expensive application process, copious paperwork and make payment in postal orders.
Suspension of visa rules was triggered by the nation's hosting of the Eurovision Song Contest in the capital, Kiev. It is supposed to be temporary, but specialists in travel to the area expect the that status to be made permanent. "The only people who benefited from the old system were corrupt diplomats," said one.
Ukraine once was as holiday camp to the USSR, thanks to its superb beaches around Odessa and along the Crimean coast. It had literally a captive audience: the Black Sea was the only warm body of water open to millions of citizens of the former Soviet bloc. The government in Kiev hopes abolition of visas will lead to an upsurge in tourism from the West. The 150th anniversary of the Crimean War has brought interest from Britain. Patrick Mercer, the Tory spokesman on homeland security and a leading military historian, led a tour to the valley that saw the Charge of the Light Brigade and the battlegrounds of Sevastapol, Alma and Inkerman. Holiday romances may also blossom, given the added appeal to many Ukrainians that a British passport seems to confer upon the holder.
Russia remains aloof from the Black Sea tourism bonanza. Although the world's biggest country owns a sizeable chunk of the coast, Moscow has shown no interest in tourism. Visa rules are no less strict than they were in the days of the USSR, and conflict in the north Caucasus means the Kremlin does not relish the prospect of an influx of British holidaymakers.
To the surprise of the travel industry, Georgia has been quick to follow Ukraine's abolition of red tape. A decree from the country's director of consular protocol removed the need for visas for citizens of EU countries, the US and Israel. The country's tourism infrastructure, once a poor joke, is improving fast: a former holding centre for refugees in the capital is being converted into a luxury hotel.
No one anticipates an immediate switch from Benidorm to the beaches around the coastal city of Batumi, but pioneering travellers are enthusiastic. Tim Burford, author of one of the first guidebooks to Georgia, calls it "one of the most heart-warming and exciting of all European destinations", and the writer Margaret Campbell reports "a wealth of cultural and historical attractions, ranging from the former capital, Mtskheta, to Gori, Stalin's home town".
Georgian cuisine is easily the best in the former Soviet Union, though, to be fair, it does not face the toughest of competition. There are still many infrastructure challenges to be overcome in Georgia; at present all telephone lines to the British embassy in Tbilisi are cut.
Across the border in Turkey, hoteliers hope to cash in on the surge in tourism; this summer, bookings from the UK have risen by 43 per cent. Most holidaymakers will head for the Mediterranean shores of Turkey, but as hotels in these resorts fill, enterprising tourists will move north to the Black Sea coast. Besides empty beaches and low prices, they will find ancient monasteries and the Ottoman town of Safranbolu, a Unesco world heritage site.
The increase of visitors to Bulgaria is causing alarm in Spain and Greece, both of which suffered a slump in UK package holidaymakers last year. The strength of the euro, and perceptions of price rises in member states, persuades bargain-hunting Britons to look further east.
Bulgaria has had cut-price holidays at its Black Sea resorts since the 1980s, but standards were poor. The best accommodation was kept for Communist Party officials, and holidaymakers suffered a dismal dining experience, despite the culinary traditions of Bulgaria (yoghurt was invented here, and it has excellent food and wine). Hotels were bady designed and run.
In the past few years, Spanish hoteliers have been brought in to raise standards and by next summer, visitor numbers from Britain are expected to double, compared with 2003. Some are hunting property, in advance of Bulgaria's membership of the EU. "Half of Bulgaria is worried about Brits arriving to buy second homes," one expatriate says. "The other half is trying to throw aged relatives out of tumbledown country homes so the houses can be put on the market."
Romania remains in the touristic Dark Ages, but an investment banker named Diwaker Singh has opened a £3.5m, 30-cabin resort in the unspoilt Danube Delta. "The delta offers the best nature experience in Europe," he told The Independent.
Even Moldova, is getting in on the act. This troubled, landlocked country, between Ukraine and Romania, has suddenly discovered a coastline. To the surprise of geographers, Moldova's department of tourism has identified a 200-yard stretch of Black Sea coast at "the south extreme pointGiurgiulesti] with the delta of the Danube river".
Maps show this is some 30 miles inland from the conventionally recognised shore of the Black Sea. And with no direct flights from the UK, a shambolic infrastructure, persisting civil strife and no beachside hotels, Moldova is not yet perceived by the mainstream tourism industry to be a major threat.
The New Riviera
Main attractions: Golden Sands, both the name of a leading resort and a fair description of the shoreline. Close by are the remains of the Aladzha monastery, and caves occupied 7,000 years ago. The city of Varna, from where British troops sailed to the Crimean War, is rapidly turning itself into a riviera-style resort.
Getting there: Charter flights operate from leading UK airports non-stop to Varna.
Foreign Office advice: "Thieves and pickpockets target holidaymakers at Black Sea coastal resorts. Most taxis are metered, but these may be rigged and foreigners are often subject to overcharging. Car-jackings are becoming more frequent."
Claim to fame: The Cyrillic alphabet, now used across Russia, was devised in Bulgaria.
Potential slogan: We invented yoghurt, and we've plenty more culture besides.
Main attractions: Once the wealthiest province of the Roman Empire, Romania has a fascinating culture plus stunning mountain scenery in the Carpathians, a fine Black Sea coastline and dazzling birdlife in the Danube delta.
Getting there: Frequent flights from London to Bucharest.
Foreign Office advice: "Corruption is widespread. There have been reports of police stopping foreign cars and demanding payment of fines in hard currency for spurious offences. Bogus policemen may also approach pedestrians and ask to check their documents as a way of stealing cash."
Claim to fame: Ilie Nastase, an even more successful tennis player than Tim Henman.
Potential slogan: Always less repressive than Albania.
Main attractions: The little-visited Black Sea coast of Turkey comprises an attractive shoreline decorated with Byzantine, Genoese, Venetian and Ottoman architecture. It is centred on the hectic but beautiful city of Trabzon, and becomes wilder further east towards Georgia.
Getting there: Frequent flights from Heathrow, Stansted and Manchester to Istanbul, from which the Black Sea coast is easily accessible by road.
Foreign Office advice: "There is a high threat from terrorism in Turkey. A number of sexual assaults have been reported in coastal tourist areas. Road conditions and driving standards can be poor. Serious traffic accidents are common particularly at night."
Claim to fame: Ataturk drew up plans for a Turkish republic in Samsun.
Potential slogan: Delight yourself with a different side of Turkey.
Main attractions: Once known as "the land on the route to all disasters", Moldova is an acquired taste. During the Second World War, almost all of the capital, Chisinau, was flattened. There is more of interest in Bendery, 45 miles south, with a 16th-century fortress and a robust local brandy.
Getting there: Connect in Vienna for the single daily flight to Chisinau.
Foreign Office advice: "Be alert to the risk of street crime and petty theft. It is useful to carry a torch after dark, as street lighting is poor. Transnistria (north-east Moldova) is not under Moldovan government control."
Claim to fame: The writer Pushkin lived in Chisinau for three years.
Potential slogan: The same latitude as Venice, but without the crowds.
Main attractions: Spectacular countryside, beautiful beaches, welcoming people and gastronomic excellence such as badrizhan nizgit - fried aubergine slices spread with a walnut and garlic paste and sprinkled with pomegranate - plus superb wines.
Getting there: British Airways flies three times a week from Heathrow.
Foreign Office advice: "Try to avoid going out or travelling after dark. You should avoid travelling alone in Georgia and take other precautions against the high levels of crime, including kidnapping."
Claim to fame: Stalin is still revered in his home town of Gori. A museum is devoted to his memory.
Potential slogan: Destination for midnight trains, boats and planes.Reuse content