After Music from Two Basses (february 1971), mostly improvised with the other British bassist, Barre Phillips, and Improvisations for Cello And Guitar (january 1971) with guitarist Derek Bailey, Holland formed a quartet with two saxophonists, the ebullient Sam Rivers and the mathematical Anthony Braxton, and drummer Barry Altschul that recorded the epochal Conference of the Birds (november 1972). Holland found an identity between two words that were widely regarded as antithetical, "avantgarde" and "melody", not to mention "swing". Instead, Holland's compositions, propelled by one of the most swinging rhythm sections of the time, penned by a melodic talent worthy of Debussy, and never shy of venturing into dissonant, jarring and abrasive territories. Some abstract pieces (Four Winds) had virtually no identity, others sounded like a surreal and lyrical form of hard-bop (Q & A, Interception) and others even echoed folk music (the two shortest pieces, Conference of the Birds and Now Here, both with flute). The "sound" of this album (that became the sound of the German label ECM) was going to be more influential than anything done since Davis' conversion to electrical instruments.

In 1975 Holland, guitarist John Abercrombie and drummer Jack DeJohnette formed the all-white Gateway trio. Gateway (march 1975), with Holland's May Dance and DeJohnette's psychedelic Sorcery I (and the short drum-less ballad Jamala), and 2 (july 1977), with the 16-minute group improvisation Opening. This music was a close relative of progressive-rock.

Holland's aesthetic crystallized with the two solo albums Emerald Tears (august 1977) for solo bass and Life Cycle (november 1982) for solo cello, both fragmented into short pieces. The latter, perhaps his zenith as a composer, adopted the intimate, humble, restrained stance of zen Buddhism (the five-movement suite Life Cycle) while reminiscent of medieval folk music (Rune, Troubadour Tale, Chanson Pour la Nuit).

In 1982 Holland also formed his Quintet, featuring British trumpeter Kenny Wheeler, trombonist Julian Priester, altoist Steve Coleman and drummer Steve Ellington. Holland's compositions on Jumpin' In (october 1983) were longer and livelier (Jumpin' In, New-One, You I Love) but actually simpler. Holland was even less relevant on Seeds of Time (november 1984), that featured only three of his compositions, although he regained some of his relevance on The Razor's Edge (february 1987), thanks to his Razor's Edge and Blues for C.M. (contrasted with Coleman's Vortex).

The trio with Jack DeJohnette and Steve Coleman, Triplicate (march 1988), fared better, thanks to Rivers Run and Triple Dance (and to Coleman's effervescent form). On the other hand, the quartet with Steve Coleman, trombonist Kevin Eubanks and drummer Marvin Smitty Smith Extensions (september 1989) was even more accessible than the Quintet and penned Holland's The Oracle, Coleman's Black Hole, and Eubanks' Nemesis and Color of Mind. Holland' second solo, Ones All (may 1993), was also a retreat from the "avantgarde", sounding very traditional in comparison with the first one.

The Gateway Trio reformed and recorded Homecoming (december 1994).

A new quartet with vibraphonist Steve Nelson, altoist Eric Person and drummer Gene Jackson recorded Dream of the Elders (march 1995) that contained several lengthy Holland originals (The Winding Way, Claressence, that would remain one of his most popular themes, Lazy Snake, Ebb & Flo, Dream of the Elders). This music was now elegance for the sake of elegance.

Eubanks, saxophonist Steve Wilson and drummer Billy Kilson joined Nelson and Holland for Points of View (september 1997), a collection that showed Holland the composer and arranger in a state of supreme confidence, eclectic and baroque, and best in the melancholy mood (The Balance, Mister B., Bedouin Trail, Ario, Herbaceous, Eubanks' Metamorphos). Prime Directive (december 1998), with Chris Potter replacing Wilson, was beginning to sound like the meditation of an aging man on his own form of art, resulting in the sophisticated routine of Wonders Never Cease, Looking Up, Jugglers Parade (as well as Eubanks' A Seeking Spirit). While a bit less imaginative and spontaneous than the albums of the 1980s, these last quintet works were no less austere and profound. Having invented the new "mainstream" sound, Holland now relished in being the reactionary within his own revolution. Holland seemed to be getting tired of his own game on Not for Nothin' (december 2000), that featured Eubanks' Global Citizen but few Holland originals (mainly Lost and Found and What Goes Around).

A big band performed several of Holland's originals on What Goes Around (january 2001). The Quintet performed extended versions of others on Extended Play: Live at Birdland (november 2001).

A second work for big band, Overtime (november 2002), was highlighted by Holland's most ambitious composition, the Monterey Suite in four movements (Bring It On, Free For All, A Time Remembered, Happy Jammy).

Critical Mass (december 2005) returned to the quintet format with a set of complex and intricate compositions.

Pass it On (2008) was an eclectic work for sextet.

The live Pathways (january 2009) introduced an octet with Antonio Hart (alto sax, flute), Chris Potter (tenor sax, soprano sax), Gary Smulyan (baritone sax), Alex Sipiagin (trumpet, flugelhorn), Robin Eubanks (trombone), Steve Nelson (vibraphone, marimba) and Nate Smith (drums).

Hands (march 2009) was a collaboration with flamenco guitarist José Antonio Carmona Carmona and his quartet.

Dave Holland debuted Prism, a quartet with Craig Taborn (piano and Fender Rhodes) Kevin Eubanks (guitar) and Eric Harland (drums), on Prism (june 2012).

Dave Holland formed Aziza in 2014 with Chris Potter (tenor and soprano saxes), Lionel Loueke (guitar, vocals) and Eric Harland (drums). They debuted with Aziza (september 2015).

Dave Holland recorded Thimar (march 1997) with saxophonist John Surman and Tunisian oud master Anouar Brahem. The collaboration with Brahem was resumed for Blue Maqams (may 2017), seven years in the making, that also featured Jack DeJohnette (drums) and Django Bates (piano).

The double-disc Uncharted Territories (may 2017) documents the quartet of Dave Holland (bass), Evan Parker (tenor sax), Craig Taborn (piano, organ, keyboards, electronics) and Ches Smith (percussion).

Holland formed the Crosscurrents Trio, first documented on Good Hope (september 2018), with saxophonist Chris Potter and tabla player Zakir Hussain .

Kenny Barron (piano), Dave Holland (bass) and Johnathan Blake (drums) recorded Without Deception (august 2019).

Another Land (september 2019) was a collaboration with guitarist Kevin Eubanks and drummer Obed Calvaire.

Holland, guitarist John Scofield, saxophonist Joe Lovano, and drummer Al Foster (a Miles Davis veteran) recorded Oh! (july 2002), credited to Scholohofo.