'Ah, Odessa,' an acquaintance from Russia rhapsodised when I told her that I was off to the Ukrainian city - or the 'pearl of the Black Sea', as the brochures have it. 'It's so romantic. You should just walk around: the courtyards, the streets, the sea.' Once the third city of old Russia after Moscow and St Petersburg, it's like Rio to the Russians, who flock here for its warm climate, beaches, cafes and nightlife - and quite possibly for its historic buildings, culture and chess.

Could it be a weekend break for the British? Well, why not? Odessa's in Europe, although you can't fly directly. And it's a great enigma: the very name 'Odessa' is full of Cold War romance. I went via Budapest to find out more.

Odessa's airport didn't disappoint. Like something from a le Carré novel, it was white, rectilinear and staffed by knuckleheads in green uniforms. The time they spent rubberstamping my passport smelled of the KGB. But I emerged, met my driver and sped - truly sped - through the sunny boulevards and Stalinist blocks of suburban Odessa to the Chorne More Hotel, a smoked glass ex-Intourist pile tweaked into the market era but retaining a bracing touch of anti-service. The receptionist kept my passport for 20 minutes. Why? She gave me a look that said: 'None of your business, buster.'

The cobbled streets, lime trees and noble but desiccated buildings made for a pretty sight. I had a beer in the bar and went to the hotel's sanitorium. In a UK spa, you get backlit twigs and whale song. Here a middle-aged guy with hands like hams pummelled me and finally spoke. 'Where from?' 'London.' 'I have been,' he growled. 'Tilbury!' Of course: Odessa was always a key Russian port.

I explored Odessa's central grid of streets, faintly redolent of New York. The cobbles, plane trees and wide (if cracked) pavements gave on to a new economy of internet cafes, fashion shops and bars towards the centre. Sailors swaggered around whistling at girls.

Great fun. Yet through the gloaming I could also see an older Odessa, where little old ladies hauled faggots of firewood home and old fellows dipped wheelie bins. These ghost-like individuals, mostly elderly, represented a generation that had lost to the market. I dived into a couple of Odessa's handsome onion-domed Orthodox churches, near the impossibly grand railway station, and saw a devotion scarcely even seen in southern Italy.

Ann turned up in the morning to show me round Odessa. I had explained that I wanted a young guide to help with bar research and when she turned up, I shouldn't have been surprised at her pink nail varnish, short skirt and general pulchritude.

In 'Back in the USSR', the Lennon-McCartney lyric goes, 'The Ukraine girls really knock me out', and I soon learnt that Odessa's women are a tourist attraction in their own right, encouraged by a demi-monde of matchmaking websites catering for chaps of a certain age. At breakfast, discussing the day's museum plans with a nice German family, a hefty lone English gent at the next table piped up: 'You're missing out the best sight of all: the bloody women!'

Ann and I walked down leafy avenues to Odessa's centre to see the baroque Opera House. Odessa was impressive architecturally, like St Petersburg in a Mediterranean-style climate. It celebrated its 200th anniversary in 1994, harking back to the date when Catherine the Great decided it was a useful harbour and up it went, a neo-classical new town. It's fallen on harder times, but has still got the feeling of a set-piece city, such as Bath.

We looked at this Albert Hall of the Near East and the Mozart Hotel opposite, catering for Odessa's new money, then walked further into grand streets full of ornate Art Nouveau apartment blocks that had been bought back to life. Ann was encouraged. 'There,' she said proudly, 'is our first Armani shop.'

The streets gave onto the Primorsky Boulevard, which had a great view of the new port, where Russian cruise liners docked on the glittering Black Sea. We passed the statue of Alexander Pushkin, who hung out here in the 1820s, and the Museum of Archaeology, which was closed. Very Soviet. But at least I managed to see the great Ship Museum.

Primorsky offered a thriving economy of traders holding iguanas, pythons and small crocodiles with a Polaroid camera, the idea being that you posed holding them. Fending them off, at last we were at Odessa's key sight - indeed, the only sight most of us know - the Potemkin Stairs. Most will know the 192 steps from Sergei Eisenstein's 1925 film classic The Battleship Potemkin , and I felt that the traders should drop the crocs and instead bring a pram to recreate the film's most famous scene. (You'd have to be careful at the bottom though, where there's a main road that's like a racetrack for ancient Ladas.)

We walked back up the stairs past the statue of Duke of Richelieu - the French hero of Odessa, who served in the Russian army against the Turks - and stopped for a coffee at the Déjà Vu. One of the stranger facets of Ukraine's market transition has been to encourage a glut of theme bars and Déjà Vu's shtick was to have a 'Communist' bar: the past truly satirised. Meanwhile, the real past was tragically neglected. At the eastern end of Primorsky was the Vorontsov Palace, an ochre Palladian-style mansion. Once it would have been Odessa's Buckingham Palace, but near-derelict and covered in graffiti, it was a casualty of recent history.

Back at the main drag, Derybasivska, I saw the Pasazh shopping mall, where trainers were sold beneath baroque statuary, and walked in a park with a tourist market selling folksy tat. Then it was time to sit down at the unbelievably folkloric Kymahel restaurant, where I had a fabulous borscht, before taking a cab back to the hotel, which involves sticking your hand out to any driver. The charming guy who stopped wanted to talk. 'Where from?' he asked, turning around in the seat to offer his card. 'London.' 'I have been,' he said. 'Tilbury!'

Back at the hotel, I met Andrew Evans, author of the Bradt Guide to Ukraine , who loved Odessa. 'It's a port, and it's got that Marseille, Naples thing to it. It's very cosmopolitan.' Indeed, there were Russians, Greeks, Romanians, several Turkish bars, a mosque and a synagogue near to my hotel. Odessa had always been a crossroads. But there had been tragedy, too. The famine of the 1920s and the war killed a lot of Odessites, mainly Jews. It became Soviet in 1944. I had the feeling Odessa hadn't recovered yet from the 20th century.

Andrew was leading a British tour group, and I drove with them past the enormous regimented beaches that run from Odessa up the coast for 10 miles. Of my companions, one had been to see the site of her grandmother's shtetl (just like the hero of Jonathan Safran Foer's Everything is Illuminated, in which a New Yorker searches for his grandfather's village) and the next day they were off to Yalta and then Crimea, to see where the Charge of the Light Brigade faltered 150 years ago. Ukraine tends to attract the special-interest tourist.

Later Andrew and I ended in Friends and Beer, a basement bar with a bizarre menu including roast beef and Yorkshire pudding - almost an English theme bar. It was during Euro 2004 and we couldn't get a seat. I pointed to an empty table and asked for a glass of wine. The waitress shook her head. Is this typical? 'You'll get that for a while, then they'll suddenly come up with something,' said Andrew. The customer is always wrong, but soon we were applauding Russia against Spain with a local, Igor.

In 10 years' time? Well, Ukraine (never the Ukraine) is one of the fastest growing economies in Europe. The sanitoria of the Black Sea are diversifying into plastic surgery. Sooner or later, a direct flight will come. God forbid, perhaps the stag nighters will arrive. In the meantime, if you're into pioneering Eastern European cities, Odessa scoops Tallinn or Riga. And unlike other Eastern cities, it made me feel foreign. Homeward bound, I was dropped at Odessa airport and noticed a crowd outside the terminal. The cause of the diversion? A dancing bear in a cage. It wouldn't happen at Gatwick.

Factfile

Oliver Bennett travelled with Regent Holidays (0117 921 1711, www.regent-holidays.co.uk). Three nights at the Chorne More (Black Sea) Hotel is £490 per person, based on two sharing, including breakfast, flights with Malev Hungarian Airlines via Budapest and all air taxes.