Pierwszą pracą, poza okazjonalnymi koncertami w klubach Smal's i Club 125, było zastępstwo pianisty Birdland Club - Buda Powella. Inne zastępstwo, za Dona Abneya, który w końcu lipca 1956 miał na Newport Jazz Festival akompaniować Elli Fitzgerald, choć trwało tylko miesiąc zaowocowało późniejszą długoletnią współpracą z pieśniarką.
W 1957, jako członek zespołu J.J. Johnsona, wyjechał na serię koncertów do Europy. Tam nagrał swój pierwszy album Overseas. Towarzyszyli mu muzycy, z którymi grał u Johnsona: kontrabasista Wilbur Little i perkusista Elvin Jones. Na przełomie lat 50. i 60. wspólne występy proponowali mu często: Oscar Pettiford, J.J. Johnson (1956-1958), Harry „Sweets” Edison (1959-1960) i Coleman Hawkins (1961).
Na początku lat 60. Flanagan występował w nowojorskim Five Spot Club (razem z basistą Percym Heathem i Jimem Hallem na gitarze). Brał też udział w nagraniach kolejnych płyt, bowiem zapraszał go studia Wes Montgomery (1960) czy Coleman Hawkins (At Ease With Coleman Hawkins, 1960).