The first musical work for which he is remembered was his role as bassist in the trio Joseph Holbrooke, alongside guitarist Derek Bailey and drummer Tony Oxley. The trio began by playing relatively traditional jazz before moving into free improvisation. However, Bryars became dissatisfied with this when he saw a young bassist (later revealed to be Johnny Dyani) play in a manner which seemed to him to be artificial, and he became interested in composition instead.
Bryars's first works as a composer owe much to the so-called New York School of John Cage (with whom he briefly studied), Morton Feldman, Earle Brown and minimalism. One of his earliest pieces, The Sinking of the Titanic (1969), is quite an indeterministic work which allows the performers to take a number of sound sources related to the sinking of the RMS Titanic and make them into a piece of music. The 1994 recording of this piece was remixed by the Aphex Twin as "Raising the Titanic" (later collected on the 26 Mixes for Cash album).