The scene resembled a musical audition. Elvis raised his arm and looked quizzically at his only accompanist, keyboards player Steve Nieve, as if to ask "Now?" before delivering the opening line to Toledo, one of the heartbreakers from his collaborative album with Burt Bacharach, Painted From Memory.
For the judges — the audience — the moment was apt. While Costello was preaching to a predominantly converted public, there was still the question of how they would react to this stripped-down version of the man's history and his recent, plaintive endeavours with Mr Smooth. Nobody need have worried.
To lesser musicians — but particularly lesser songwriters — the use of just voice, piano and guitar would render much of their earlier, band-oriented material one-dimensional, but here the acoustic approach opened up old songs such as "Veronica," "Radio Sweetheart" and "I Don't Want to Go to Chelsea" to previously unheard nuances and subtleties. It also left plenty of room for Costello's distinctive and still impressive voice to dominate.
The Bacharach co-writes were best suited to this simple approach. Stripped of their lavish arrangements, songs such as "Toledo," "In the Darkest Place" and "I Still Have the Other Girl" emphasised the melancholy in Costello's vocal while Nieve masterfully created the dynamics on the keys.
The former Attraction, given that he had to act as the foundation and the melodic counterpoint to his partner, occasionally crossed the line into Rachmaninovian melodrama (although he looked more like John Cale) but his arrangements, particularly on "Watching the Detectives" and "Temptation," were assured and powerful.
Given that it's 22 years since Costello first came to prominence, it is testimony to his craft that he could have played a completely different set of songs and still commanded the four encores he received here. The material he did choose was beyond reproach.
He opened the set with "Accidents Will Happen," launching into it on acoustic guitar before the audience had time to acknowledge his presence. This segued nicely into "24 Hours From Tulsa," an early nod to his soul-brother Burt's early songwriting skills which in turn introduced their "In the Darkest Place."
Fans of his early product were not disappointed either, with excellent readings of "Alison," "Red Shoes" and "Radio Sweetheart." This was a relaxed, confident performance — and an intimate one — with Costello explaining the origins of songs and encouraging the crowd to join in on choruses ("Radio Sweetheart"/"Jackie Wilson Said" turning into a singalong of music hall proportions).
There were no bad performances here, just degrees of greatness. "I Want You," "Shipbuilding" and one of his best recent songs, "All This Useless Beauty" all bear his lyrical genius and were dramatic in the extreme.
The encores provided further delights, including "Oliver's Army" and "God Give Me Strength," and when he returned for the final time it was to ignore the microphone altogether and sing "Unexpected," from Mighty Like a Rose, from the front of the stage. No one stirred and it was a powerful, even moving, few minutes.
The King may be dead, but Elvis is still very much alive.
Elvis Costello performs in Melbourne tonight, Adelaide on Sunday and Perth on Monday.