Od 1964 Trzaskowski zapraszał Stańkę na zagraniczne koncerty swojego kwintetu (w Belgii i krajach skandynawskich). W tym samym roku trębacz dwukrotnie grał na Jazz Jamboree: z Trzaskowskim i Komedą. W 1966 wydany został album Komedy Astigmatic, z udziałem Stańki. W 1967 doszło ponownie do podwójnego występu na Jazz Jamboree. Stańko koncertował z grupą Komedy, ale i z własnym kwartetem, w którym grał z Januszem Muniakiem (saksofon tenorowy), Janem Gonciarczykiem (kontrabas) i Januszem Stefańskim (perkusja).
Jako lider Na początku 1968 Komeda wyjechał do Stanów Zjednoczonych, a Stańko działał jako lider zespołu, który powiększono o skrzypka i saksofonistę altowego Zbigniewa Seiferta. Na Jazz Jamboree ’68 muzyk zaprezentował już Tomasz Stańko Quintet, który szybko zdobył uznanie i sławę. Najpierw w Polsce, a po debiucie na scenie międzynarodowej – występie na berlińskim festiwalu Berliner Jazztage ’70 – był rozpoznawany także w Niemczech i reszcie Europy. Po odejściu Gonciarczyka basistą grupy został w 1969 roku Bronisław Suchanek, i od tego czasu – aż do zakończenia działalności w 1973 roku – skład kwintetu nie uległ już zmianie.