"Cry Baby Cry" was the third U.S. single and the second international single from Santana's album All That I Am. It was also the fourth international single from Paul's third studio album, The Trinity (2005). However, it did not appear on the original issue of the album, only on the 2006 re-release that contained a bonus disc with the track. The song does not appear on any Stone album.
The single was released in the United Kingdom on May 8, 2006, and was the biggest hit from Santana's album, despite peaking at number seventy-one on the UK Singles Chart and spending only one week inside it. However, it fared better than the previous single, "Just Feel Better", which missed the chart completely. It was the smallest hit from Paul's album though and his first single to miss the UK top forty, as well as the first single to miss the top forty for Stone.