Costello's career-long mission to explore fresh musical worlds has built one of the most intriguing and enduring catalogues of any songwriter from the rock 'n' roll tradition.
On the opening night of his Australian tour, he showed he could take the rich diversity of colours from his palette — rootsy rock 'n' roll, classic pop, soul, folk, Sinatra-esque ballads, country and anything else that takes his fancy — to create a spellbinding two hours that transcended mere entertainment.
This is music that swings from the deepest shade of blue to the rapturously uplifting.
Accompanied by his own guitar and reunited with his original keyboardist Nieve at the piano, Costello dipped into most corners of his voluminous songbook.
He ranged from the first song he recorded, "Radio Sweetheart" — segued here into Van Morrison's "Jackie Wilson Said" — through to the lingering torch ballads from last year's collaboration with Burt Bacharach, Painted From Memory.
In between the pair visited cherished gems such as "Alison" and "Accidents will Happen," as well as neglected ones such as "Almost Blue" and "God's Comic."
Some of the new songs were delivered in fresh arrangements to suit the duo. "Temptation," for instance, was stripped of its soul music beginnings and embellished with Nieve's classical flourishes.
Others, such as "Watching the Detectives" and "I Don't Want To Go To Chelsea," were delivered with the same blazing intensity the pair conjured up with the Attractions when they first played here 20 years ago,
Nieve was a revelation throughout, effortlessly mixing classical technique with funky rock 'n' roll piano, sometimes in the course of a few bars.
Costello has developed his voice from the bitter delivery of his youth into an expressive instrument worthy of the demands of his newest songs, which have as much in common with Sinatra's In the Wee Small Hours as they do with Bacharach's pop smashes.
If there is a criticism of Costello's material in the '90s it's that punning wordplay comes so easily to him that it can weigh down the songs.
But there's no such problem with the tales of heartbreak on Painted From Memory, where Costello's lyrical and melodic gifts are as sharp as ever.
This was illustrated by his delivery of "This House Is Empty Now," where a man walks the bare rooms of his house on the eve of his divorce.
It's not the stuff of No 1 hits or This Year's Models — it's songwriting craft that's built to last.
To borrow a vivid Costello phrase, this was an evening of blood and chocolate.
And judging by the reaction from the house, there won't be too many present who aren't already looking forward to the day when Costello and friends pass this way again.