Flanagan also first accompanied Ella Fitzgerald in 1956, for around a month, including at the Newport Jazz Festival. Later that year he joined trombonist J. J. Johnson, with whom he recorded several albums in 1957 and then toured Europe. While in Sweden, Flanagan, with bassist Wilbur Little and drummer Elvin Jones, recorded his first album as leader, "Overseas". Late in 1957 he was part of Miles Davis' band for a short period, before returning to Johnson early the following year, for another stay of 10 months. A period leading his own trio in 1958 was followed by joining trombonist Tyree Glenn.