In 1957 Byrd met double bassist Keter Betts in a Washington, D.C., club called the Vineyard. The two began doing gigs together, and by October they were frequently performing at a club called the Showboat. In 1959 the pair joined Woody Herman's band and toured Europe for three weeks as part of a State Department-sponsored goodwill tour. The other members of the band were Vince Guaraldi, Bill Harris, Nat Adderley and drummer Jimmy Campbell. Byrd led his own groups that sometimes featured his brother Joe. Byrd was also active as a teacher in the late 1950s; he trained guitar students at his home in Washington, D.C., each required to audition before he agreed to be their teacher.