Commissioners and performers of Coleman’s work include clarinetist David Krakauer/Concert Artists Guild (The Kaspar In Me, 1985), accordionist Guy Klucevsek (Below 14th Street/Above 125th Street, 1987), Relâche (The King of Kabay, 1988), pianist Joseph Kubera (the hidden agenda, 1989), The Crosstown Ensemble (Latvian Counter-Gambit, 1992), Neta Pulvermacher and Dancers/Meet The Composer (Goodbye and Good Luck, 1993), Bang on a Can All-Stars/Jerome Foundation, (Mise en Abîme, 1997), Kitchen House Blend (Lapidation, 2002), guitarist Marco Cappelli/Associazione Alessandro Scarlatti (The Buzzing In My Head, 2003), TILT Brass Band (Set Into Motion, 2005), the Ruhr Triennale (Dubistmeinichbindein, 2007), the Brecht Forum (Artifacts for String Quartet, 2008), Merkin Concert Hall (Flat Narrative, 2008), the Festival Banlieues Blues/Ensemble Erik Satie (Echoes From Elsewhere, 2011), ISSUE Project Room/ String Orchestra of Brooklyn (Empfindsamer, 2012).

Other key works include the cycle by Night (1987–1992), a series of works inspired by Coleman’s experiences in (the ex-) Yugoslavia (CD Disco by Night, Avant 1993). Coleman has presented his own work at the Sarajevo Jazz Festival (Bosnia), North Sea Jazz Festival (Holland), Saalfelden Festival (Austria), and the Krakow and Vienna Jewish Culture Festivals.

Ensembles led by Coleman have recorded extensively for Tzadik and include the trio Sephardic Tinge (Sephardic Tinge, 1995; Morenica, 1998; Our Beautiful Garden is Open, 2002) and Selfhaters Orchestra (Selfhaters, 1996; The Abysmal Richness of the Infinite Proximity of the Same, 1998). Coleman has also toured and recorded with John Zorn, Elliott Sharp, Marc Ribot, Shelley Hirsch, Roy Nathanson, and many others.

Coleman has been awarded grants from New York Foundation on the Arts (1988 and 2006), New York State Council on the Arts, and Meet the Composer. He has received residencies from the Yellow Springs Arts Center (1987 and 1990), the Djerassi Colony (1989), the Frei und Hansestadt Kulturbehörde of Hamburg, Germany (2002), and the Civitella Ranieri Center, Umbertide, Italy (2003), the Centro Veneziano di Studi Ebraici Internazionali in collaboration with Venetian Heritage (2011).

Coleman has recorded 13 CDs under his own name, and he has played on more than 100 CDs. His most recent CDs are The End of Summer (Tzadik), which features his NEC Ensemble Survivors Breakfast, Shmutsige Magnaten (Tzadik), a live solo performance from the 2005 Krakow Jewish Culture Festival that features interpretations of the songs of Mordechai Gebirtig; Pushy Blueness (Tzadik) and Lapidation (New World), both recordings of his chamber music, and Freakish: Anthony Coleman Plays Jelly Roll Morton (Tzadik, 2009). His Damaged by Sunlight (2010) was issued on DVD by the French label La Huit.