The album spawned three singles: "The Line Between the Devil's Teeth (And That Which Cannot Be Repeat)", "Cuts You Up" and "A Strange Kind of Love". The track "Cuts You Up" became a modern rock hit in 1990, spending seven weeks at the top of the U.S. charts and crossing over to Billboard Hot 100, where it peaked at number 55. The other singles also charted on the Modern Rock Tracks chart, peaking at numbers 18 and 21, respectively.
Ned Raggett of Allmusic praised the album, stating that "Deep showed Murphy balancing mass appeal and his own distinct art with perfection." He also wrote: " Murphy simply sounds like he's having the time of his life, singing both for the sheer joy of it and for the dramatic power of his commanding voice."