La canzone è inizialmente una collaborazione solo tra Sigsworth e Jem che iniziava in quel periodo a lavorare sul suo album di debutto. Dopo due giorni di lavoro in studio i due hanno scritto la canzone Silly Thing. La canzone è stata poi suonata con Sigsworth per Madonna che ha aggiunto e cambiato alcune parti tra cui anche il titolo che è diventato Nothing Fails.
Nothing Fails è una canzone d'amore nella quale si fa ampio uso della chitarra acustica con un testo che parla di una persona innamorata, alla quale qualsiasi cosa non può andare male proprio perché è innamorata.
Il London Community Gospel Choir diretto da Nicki Brown, ha registrato le voci in sottofondo della canzone per darle un sound gospel.
«Quando alla fine ho sentito la canzone finita è stata un'esperienza stranissima. Non è da tutti i giorni sentire Madonna cantare parole e melodie che hai cantato a due nel tuo dittafono al mattino. La ammiro veramente perché è molto coinvolta in ogni cosa che fa. La canzone è bellissima[2]»
Il singolo di Nothing Fails, originariamente pensato come doppio CD singolo insieme a Love Profusion, è stato realizzato negli USA e in parte dell'Europa nell'inverno del 2003 (non è uscito nel Regno Unito).
In una versione europea del singolo è contenuta anche Love Profusion.
Non è stato prodotto alcun video del brano. Prima dell'annuncio della casa discografia, si era vociferato che il regista Steven Klein si fosse proposto per realizzare il video della canzone e alcune indiscrezioni facevano trapelare che Madonna volesse realizzare un video di ispirazione religiosa in Israele.