He began opening for celebrities including Judy Garland, Patti Page, Nat King Cole, Billy Eckstine, Lena Horne and Tony Martin. When Martin was cast in the movie "Hit the Deck", he suggested King for a part, which resulted in his first movie role. King played small roles in movies in the 1950s, but disliked playing stereotypical roles that he described as "always the sergeant from Brooklyn named Kowalski".. Typical of this was his role as Sgt Buzzer in the WW2 film On the Fiddle (1961).