As of December 1955 Elvis had still not made an appearance on national television. His manager Colonel Tom Parker negotiated a deal through Steve Yates with CBS's "Stage Show" for four appearances on the show in January 1956 at $1,250 each and an option for two more at $1,500 each.
Harry Kalcheim, an agent with William Morris Agency, which represented Elvis, was upset that Parker had booked Elvis through another agent. Colonel Parker, in a straightforward letter written December 16, 1955, chastised Kalcheim for his lackluster attempts to book Elvis. Colonel told him that writing a letter and then sitting back and waiting to hear a reply was no way to sell Elvis. He continued, "If I waited for someone to call me with deals all the time, I would have to start selling candy apples again. Nuff said..."
On Monday, January 23, 1956, Elvis, Scotty, Bill and D.J. rehearsed in Memphis for their television debut. Elvis and the Colonel flew to New York on Wednesday the 25th. They stayed at the Warwick Hotel on 52nd Street. Scotty, Bill and D.J. drove from Memphis to New York and arrived on Friday, January 27th.
"Stage Show" was produced by Jackie Gleason and hosted by big band leaders Jimmy and Tommy Dorsey. The thirty-minute program aired on Saturday nights at 8:00 PM as a lead-in to Jackie Gleason's "The Honeymooners."
Elvis and his band rehearsed at Nola Studios in New York on the morning of Saturday, January 28th. That night the show aired from CBS Studio 50. It was raining and the then-unknown Elvis Presley did not draw a large studio audience. Also appearing on the show were singer Sarah Vaughan and comic Gene Sheldon. Tommy Dorsey introduced Cleveland disc jockey Bill Randle, who, in turn, introduced Elvis to his first national audience by saying:
"We'd like at this time to introduce to you a young fellow who, like many performers - Johnnie Ray among them - came out of nowhere to be an overnight big star. This young fellow we saw for the first time while making a movie short. We think tonight that he's going to make television history for you. We'd like you to meet him now - Elvis Presley."
Elvis wore a black shirt, white tie, dress pants with a shiny stripe, and a tweed jacket. He sang a "Shake, Rattle & Roll / Flip, Flop & Fly" medley and "I Got a Woman." The audience reacted with both shock and interest. The show received an 18.4 % ratings share while its competition "The Perry Como Show" on NBC received a 34.6% share. The option was picked up and Elvis appeared a total of six times on "Stage Show."
For these appearances the band rented instruments in New York while Elvis associates Red West and Gene Smith transported the band's own instruments to the next concert appearance using a pink trailer that Elvis' father Vernon had built for this purpose. After the fourth "Stage Show" the rented standup bass that Bill Black had enthusiastically played had to be repaired. Bill had broken the neck, sound post and the back of the instrument. The repairs cost $32.96.
Elvis' sixth and final "Stage Show" appearance was on March 24, 1956. That night Carl Perkins was to have been on the opposing "Perry Como Show." However, Carl had been badly hurt in an automobile accident on the way to New York. That night on "Stage Show," out of respect for his friend Carl, Elvis refused to sing Perkins' "Blue Suede Shoes" as previously planned and instead sang "Money Honey."