Almeida was first introduced to the jazz public as a featured guitarist with the Stan Kenton band in the late 1940s during the height of its success. According to author Michael Sparke, Almeida and his fellow Kenton bandmember drummer Jack Costanzo "endowed the music of Progressive Jazz with a persuasive Latin flavor, and the music is enriched by their presence." Famed Kenton arranger Pete Rugolo composed "Lament" specifically for Almeida's cool, quiet sound, and Almeida's own composition "Amazonia" was also featured by the Kenton orchestra. Almeida stayed with Kenton until 1952.