That must have been the Stiff Records tour that he did with Ian Dury, Graham Parker, Nick Lowe and some others (not sure if it was '75 or '76).
The Beeb broadcast film of that tour on a great 2-part Stiff Records documentary quite recently (along with a whole heap of vintage Stiff Records performances from Dury, Madness, Kursaal Flyers etc) . Elvis pretty well came into Stiff's office from the street, pretty well unknown but he was a major hit on the tour.
He also did appearances later on at Ronnie Scotts of course, along with Chet Baker.