Throughout the late 1950s and early 1960s Flanagan made frequent appearances in recording studios, for a large number of leaders and record labels. In May 1959 he was part of a groundbreaking recording: John Coltrane's "Giant Steps", described by "The Penguin Guide to Jazz" as the saxophonist's "first genuinely iconic record". The technical complexity of the music, particularly of the title track, meant that there were numerous false starts and rejected takes, and the initially released take of "Giant Steps" is a rare instance on record of Flanagan sounding uncertain. Another appearance on a landmark recording came in January of the following year: Flanagan was a member of the quartet that made "The Incredible Jazz Guitar of Wes Montgomery"; his playing complemented that of the guitarist, using controlled force on bebop numbers and delicacy on a ballad track.