Alice's first appearance on 'The Tonight Show' was on November 24th 1975 with guest host McLean Stevenson (who played Colonel Blake in M.A.S.H.).

He's second appearance on the show, with Johnny Carson, is the famous one. He appeared to publicise the then current 'Lace And Whiskey' LP. He performed the title cut in '40's gangster gear and tommy gun, with the giant chickens from the stage show.

On July 31st 1997, Alice appeared on 'The Tonight Show' again, this time with Jay Leno. He performed 'I'm Eighteen', and this was the first public appearance of Alice playing a guitar. He was not interviewed this time as the producers seemed to think that a woman with an iguana was more worthy of the air time!

"Alice was booked primarily as a musical guest with the possibility of an interview segment. The show had strong intentions on an interview segment. They did a pretty extensive pre-interview with him before the show. Dennis Miller is basically Jay's personal best friend so I guess he wasn't about to cut him short. I don't know why the lizard segment was so long.
I truly believe both the producers and Jay were disappointed that they ran out of time. True, it is standard for Jay (or Johnny or Letterman) to invite a guest back who was cut short... but Jay asked Alice to come back no less than 3 times and that was off camera. The producer of the musical segment did the same. They said that they loved the stuff in the pre-interview (Alice's friendship with Groucho Marx was one of the anecdotes brought up) and would love to have Alice back on anytime.
(Renfield, October 1997)

There was a lot of discussion about why Alice did 'I'm Eighteen' on the Tonight Show that year. Just for the record:

"It wasn't his first choice by any means. He wanted to do either 'Under My Wheels' or 'No More Mr Nice Guy'. Problem was that neither of those songs appear on the US version of 'A Fistful Of Alice' which was something of a prerequisite. 'School's Out' would have been more predictable and tired than 'I'm Eighteen'. 'Poison' is a difficult song to do live because of the background vocalizing so that was ruled out. 'Is Anyone Home' would have been almost too unrecognizable and 'The Tonight Show' is very intent on guests doing a recognizable song, or a current single (that song was never released as a single)
Alice didn't want to do 'Billion Dollar Babies' or a ballad. Doesn't leave much else from 'A Fistful Of Alice'.
(Renfield, October 1997)

On March 18th 2011 he was back on the show again, this time performing 'School's Out' with Dweezil Zappa on guitar, who happened to be sitting in with the house band that night, as well as a group of random backing singers in Alice make up. Alice appeared in full costume and make up and cane.

Then on September 9th 2011 he was back again, this time to introduce new guitarist Orianthi by playing 'I'll Bit Your Face Off' with the touring band from the 'Welcome 2 My Nightmare' album.