Since then, Kayo Dot's music has undergone several identity shifts, largely influenced by the band's constantly-changing lineup and instrumentation. One predominant element of Driver's compositional voice which remains consistent throughout all of Kayo Dot's output, however, is the band's use of abstract timing and performance cues. This lends to the music the element of "malleability" mentioned in Tzadik's description above.

The music of Kayo Dot is commonly categorized as post-metal, post-rock, progressive rock, or avant-garde. Their songs involve complex instrumentation (composed by singer and frontman Driver). They are substantially longer than typical rock songs, usually ranging from 8 to 18 minutes in length.

Kayo Dot was formed after the disbanding of maudlin of the Well, a progressive heavy metal band which formed in 1996 and dissolved in 2003. Many past members of maudlin of the Well – Josh Seipp-Williams, Sam Gutterman, Terran Olson, Andrew Dickson, and Toby Driver – studied at Hampshire College in Amherst, Massachusetts from 1996–2000, where My Fruit PsychoBells...A Seed Combustible was recorded. At Hampshire, Driver, Olson, and Dickson were students of jazz musician Yusef Lateef, whose theories of autophysiopsychic music may have influenced the bands' output.

Driver has gone on to say on their website: "Some members of this project worked in the progressive-metal project-band maudlin of the Well from 1996 - 2003, at which time motW dismembered. Kayo Dot isn't much different from maudlin of the Well musically - rather it's more like a continuation in the direction maudlin of the Well had been progressing."

and has also said: "People are too preoccupied with whatever connection there may be between maudlin of the Well and Kayo Dot."

In May 2005, Tom Malone joined the band as their new drummer after longtime collaborator Sam Gutterman left the band in March 2005. Kayo Dot then signed to Robotic Empire Records and released its second album, Dowsing Anemone with Copper Tongue, in January 2006.

In 2006, near the end of the fall tour, four members – playing guitar, bass, drums, and trumpet – left the band for personal reasons. On the tenth of December, Greg Massi also left Kayo Dot on good terms stating he was going "to try and figure out other aspects of my musical life and take some time to figure out where I want to be going." (Massi has since completed his solo album, "A Time for Rust" under the moniker Baliset. Massi also temporarily rejoined Kayo Dot in January 2010 as a guest for the purpose of one performance of Choirs of the Eye at The Stone (music space) in New York City on February 6, 2010).

After Massi's departure, Kayo Dot, consisting of only two members, Driver and Matsumiya, began working on their third album, Blue Lambency Downward, which was released in May 2008 by Hydra Head Records. Kayo Dot used several session musicians on this recording (Skerik on tenor and baritone saxophone and vibraphone, Hans Teuber on clarinet, Charlie Zeleny on drumset), and enlisted Randall Dunn as their producer and recording engineer. This album marked the first time one of Driver's recordings was not produced by Driver himself. After Blue Lambency Downward's release, Driver relocated from Boston to New York City, and for the purpose of touring the woodwind-abundant album, put a new lineup together whose new members were: Patrick Wolff on woodwinds, Daniel Means on woodwinds and guitar, David Bodie on drums, and original (and former maudlin of the Well) member Terran Olson on woodwinds and keyboards. Patrick Wolff has since left the band, and Daniel Means has added bass guitar to his duties.

In April 2008, Driver began working on a new long-form composition with his partner, Yuko Sueta, a NYC-based writer, filmmaker, and video artist (with Driver as the composer and Sueta as the author, intending to create a film to be projected along with performances of the music). A first draft of this piece was premiered at The Stone in September 2008 by The Kayo Dot Auxiliary Unit (Bodie and Means of Kayo Dot, Yuko Sueta, and Tim Byrnes on trumpet). Shortly thereafter, Sueta, who had been fighting breast cancer, became incapacitated by the disease. Driver re-drafted and adapted the piece for Kayo Dot (along with Byrnes), toured it in May 2009 on the road with Secret Chiefs 3, and recorded it with Randall Dunn in Seattle during June-July 2009. Sueta died while the record was in post-production, and the band has dedicated it to her. Coyote is Kayo Dot's fourth studio album and was released on April 20, 2010 by Hydra Head Records, once again featuring a surprising re-configuration of the band's instrumentation and sound.

Kayo Dot will also be releasing an EP entitled Stained Glass, scheduled to be released in November, 2010.