The sold-out auditorium shakes with a roar of approval - and, for a second, Lloyd Cole looks slightly taken aback.
The rapturous reception is not for one of the platinum-selling classics from his days with The Commotions in the 1980s. Instead, the crowd are cheering for Like A Broken Record, the opening track of his excellent but considerably lower-selling 2010 album.
"Thanks," says the singer-songwriter. "Always nice when the new songs are as popular as the old ones."
In fact everything Lloyd Cole plays over a two-hour set at Ustanova Kulture Palilula is devoured ravenously by an audience which has long been starved of live music like this.
Much of Belgrade beats to the pulse of British bands from the 1980s - blasting from shops, cafes and taxis. Street vendors and record shops offer locally-pressed vinyl copies of all the era's big albums for two or three pounds.
But seeing the acts in the flesh has been tricky since the breakup of Yugoslavia - thanks to conflict, international embargoes and economic woes.
Now things are changing. The economics of the music industry and Serbia's shift towards the European Union are playing into the hands of local listeners.
Lloyd Cole was just one of a considerable list of respected international acts who made their first visits to Belgrade in 2013. Beyonce opened her world tour at the city's main arena. Depeche Mode played an enormous outdoor show. And Green Day played at the foot of the city's ancient riverside fortress.
"I hadn't been getting offers here before - or, at least, not workable offers," says Lloyd Cole on the day of his show.
The singer admits there is a delicate balancing act for someone with his current profile - respected but not million-selling, although current album Standards has caused a considerable critical stir.
Income from touring has become vital to artists who can no longer rely on royalties from record sales. But travelling to a country where there is no audience waiting to buy tickets would be a costly mistake.
"There's a whole block of the world that starts somewhere near where the old iron curtain used to be and goes all the way to Japan that I've almost never been, and from a selfish point of view, I'd be excited to try to go to new places."
"Realistically, my chances of getting to those places would be dependent on me actually having some kind of re-emergence, which strangely seems to be happening right now."
But in Belgrade it is not just about the revival of a particular artist. Many of those for whom music is a passion are celebrating the re-emergence of their city on the international musical map - and what that means for their country.
Valentina Macura promoted Lloyd Cole's show as part of October's inaugural Festival Parallel - and says the renewed popularity of Belgrade as a tour stop has enormous symbolic significance. It indicates the decline of insular, nationalist attitudes which championed locally-made "turbo folk".
"Depeche Mode was a huge band for people in Belgrade and Serbia. When they came, and all of those countless thousands of people went to see them, it felt like after 10 years, we won!"
Valentina believes the range of touring productions coming to Belgrade shows that the city is finally recovering - culturally at least - from the isolation of the Milosevic era.
"The country is opening up - it has been for the past decade. But it's very important not just to have the big names coming, but to have artists who are a bit less commercial and more quality."
John Lydon's Public Image Limited certainly fit that description - they sparred with an enthusiastically abusive crowd in the garden of the Student Cultural Centre. Mark Lanegan - of Screaming Trees and Queens Of The Stone Age - has become a regular visitor, as has veteran singer-songwriter Chuck Prophet.
Peter Gabriel was another 2013 Belgrade debutant - making a late booking at the city's arena after a date in Croatia's capital Zagreb fell through.
His long-time guitarist David Rhodes says there are certain perils to playing in parts of the world which have not previously been fixtures on the circuit.
"Sometimes you're just not the right act to play and at the last minute the promoter will say: actually I can't afford to have you come out this far. Then you have to turn back and find something else to do!"
David Rhodes has become a frequent visitor to Serbia thanks to his involvement with the band Balkanopolis. And he says the changes in the country's international standing have come at just the right time to pick up musicians keen to expand their touring horizons and income.
"Generally artists will be pushing further east. Promoters will only put things on if they think they can make some money out of it, and artists will then come so that they can make a bit of money too.
"And I guess it's quite easy, once the promoters see it happening with a couple of people, that will then attract more and hopefully the scene will expand."
Serbia's promoters are also hoping for a little high-level help. Valentina Macura says she would like the government to provide "better conditions" for putting on events involving international artists - with tax breaks and help with sponsorship.
As it happens, the government has started to wake up to the fact that big-name gigs could be a way of attracting more overseas visitors to Belgrade - further rehabilitating Serbia's image.
Prime Minister Ivica Dacic says he has asked the country's new Minister of Culture to look into ways of attracting more international touring artists.
"It all greatly contributes to the strengthening of the position of our country. There is still much work to do, so that when you say Serbia, the first thing you think of is Novak Djokovic or the Exit Festival or the fact that the best nightlife is happening here - and not to think of Serbs as war criminals."
The past couple of decades have been turbulent both for Serbia and the international music industry. But now both sides are ready to give each other what they need. It could be the re-birth of a beautiful relationship.