La banda se formó en 1956 en Benton Harbor, Míchigan, inicialmente como the Four Sounds. La formación original estuvo compuesta por Gene Harris al piano, Andy Simpkins como contrabjista y Bill Dowdy en la batería,^[1]​ además del saxofonista Lonnie 'The Sound' Walker, que abandonó la banda al año siguiente. El grupo se trasladó primero a Washington y después a Nueva York, donde, ya como Three Sounds, realizaron una primera grabación para Riverside Records, antes de firmar un exclusivo contrato con la discográfica Blue Note.^[2]​

Entre 1958 y 1962, el grupo publicó nueve álbumes con Blue Note. Durante este periodo actuaron en numerosos clubes de jazz a lo largo de todo Estados Unidos. El trío tocó y grabó con músicos como los saxofonistas Lester Young, Lou Donaldson, Stanley Turrentine y Sonny Stitt, el cornetista Nat Adderley, la cantante Anita O'Day y el guitarrista Bucky Pizzarelli, entre otros.

• 1958: Introducing the 3 Sounds
• 1958: Introducing the 3 Sounds Vol. 2
• 1958: Branching Out con Nat Adderley
• 1959: Bottoms Up!
• 1959: LD + 3 con Lou Donaldson
• 1959: Good Deal
• 1960: Moods
• 1960: Feelin' Good
• 1960: Here We Come
• 1960: It Just Got to Be
• 1960: Blue Hour con Stanley Turrentine
• 1961: Hey There
• 1961: Babe's Blues
• 1962: Out of This World
• 1962: Black Orchid
• 1962: Blue Genes
• 1963: Anita O'Day & The Three Sounds
• 1963: Jazz on Broadway
• 1963: Some Like It Modern
• 1964: Live at the Living Room
• 1964: Three Moods (Limelight)
• 1965: Beautiful Friendship (Limelight)
• 1966: Today's Sounds (Limelight)
• 1966: Vibrations
• 1967: Live at the Lighthouse
• 1968: Coldwater Flat
• 1968: Elegant Soul
• 1969: Soul Symphony
• 1970: Live at the "It Club"
• 1971: The 3 Sounds - Gene Harris album