Sitt genombrott som lyhörd basist fick Johnson i pianisten Bill Evans trio (1978–80). I mitten på 1980-talet bildade han den kritikerrosade kvartetten Bass Desires (1985–87). Samma grundstomme återfanns i John Abercrombies (född 1944) trio (bildad 1985) fram till början av 1990-talet.