En sus tempranas grabaciones, se apoyó del guitarrista John Tropea y al flautista de Jazz fusión, Hubert Laws.
Deodato siguió grabando hasta los años 1980 bajo el sello discográfico Kenya, pero no logró alcanzar totalmente el éxito que obtuvo con Prelude.
Dos de sus canciones, Latin Flute y Super Strut, son tocadas dentro del juego Grand Theft Auto: Vice City, y pertenecen a la banda sonora del mismo juego, titulado Radio Espantoso.
Su habilidad como arreglista le proporcionaron la entrada a la industria estadounidense de la grabación, escribiendo partituras para Wes Montgomery, su compañera brasileña cantautora Astrud Gilberto y, más notablemente, para Frank Sinatra, en su álbum Sinatra & Company (que se considera dedicado al género bossa nova).
Ha colaborado también en la banda sonora de varias películas, como Bossa Nova, Ghostbusters II e incluso El exorcista.