His first improvisations were with drummer Kjell Nordeson, who would later form the AALY Trio with Gustafsson. Mats Gustafsson moved to Stockholm in the mid-'80s, and there met musicians such as Sten Sandell and Raymond Strid. The three formed Gush in 1988, two years after Gustafsson's duo with Christian Munthe, Two Slices of Acoustic Car, began. He also worked with Berlin-based Sven-Åke Johansson during this time, thus becoming acquainted with the German scene.
In 1990, Gustafsson performed in Derek Bailey's Company in London. He also began visiting the U.S. regularly, becoming a regular in the Chicago improvising community as the '90s progressed, working extensively with Hamid Drake and Ken Vandermark, among others. Gustafsson has also performed and recorded with Sonic Youth, Barry Guy, Paul Lovens, Georg Graewe, Jaap Blonk, and as a member of Peter Brotzmann's all-star Chicago Octet/Tentet.