The group first surfaced as the Jeff Ballard Trio in 2000 on one track of the anthology Originations, curated by Chick Corea (Ballard was Chick’s drummer at the time) and became Fly with the release of their first album, on Savoy, in 2004. Association between the players however goes back much further. Grenadier and Ballard played music together as teenagers in California in the early 1980s and subsequently gigged together often. They both migrated to the US’s East coast in 1990 where they met Turner, and the three musicians have played in diverse permutations and contexts since then. In Fly, Turner, Grenadier and Ballard all write material. Mark Turner: “Sometimes it’s the saxophone carrying the melody. Other times it’s the bass or drums. We spread out the frontline duties among us.
Jazz saxophonist Joe Lovano said about their interplay on the Year of the Snake-album: "Fly is a beautiful trio, they play with a wonderful clarity. And Mark plays with a brilliant execution on his horn. [...] He plays with an amazing range on his instrument. That trio has a classical approach in the way the music is written and the way they come off it in the rhythm and in the attitude they're playing. They're improvising but their dialogue is more classical in nature, the way it feels. [...] That's expression, the waves, the life forms, the wind. Fly sounds lovely and beautiful and their music has a real presence, it captures you."