Dwa lata później Roberto Carlos wystąpił w TV Tupi śpiewając piosenkę „Tutti Frutti” z repertuaru Little Richarda. Został następnie wyznaczony jako artysta otwierający koncert Billa Haleya w hali Maracanãzinho w Rio de Janeiro; poznał wówczas Erasmo Estevesa (znanego później jako Erasmo Carlos). W 1958 Roberto Carlos utworzył zespół The Snacks (przemianowany później na The Sputniks), w skład którego weszli: Erasmo Esteves, Tim Maia, Edson Trindade, Arlênio Livio i José Roberto „China”. Grupa po kilku występach telewizyjnych rozpadła się z powodu konfliktu między Carlosem a Maią. Po występie w kilku filmach oraz w kolejnym zespole, The Snakes (w którym występował razem z Erasmo), Roberto Carlos postanowił spróbować swych sił jako artysta bossa novy, będąc w tym okresie pod silnym wpływem João Gilberto. Świadectwem jego dokonań na tym polu są single: „João e Maria”/„Fora do Tom” (wydany w 1959) i „Canção de Amor Nenhum”/„Brotinho Sem Juízo” (wydany w sierpniu 1960). W tym czasie Roberto Carlos regularnie występował w programach telewizyjnych.