Timeless Journey is the fifteenth solo studio release by Patti LaBelle and her first release off Def Soul Classics notable for the hit songs "New Day" and "2 Steps Away". It was also one of her most successful albums reaching number five on the R&B albums chart and hitting the top 20 on the Billboard 200.
By 2002, Patti LaBelle had been with MCA Records for seventeen years. The label had helped to increase LaBelle's popularity with both pop and R&B audiences resulting in a platinum album and four subsequent gold-selling follow-ups. However, LaBelle's last album with the label, 2000's solemnly-produced When a Woman Loves failed to generate a hit record or even go gold. In 2003, MCA Records was absorbed by Geffen Records. As a result, LaBelle signed with The Island Def Jam Music Group's Def Soul Classics division, joining The Isley Brothers as the two first acts on Antonio "L.A." Reid's new Def Jam imprint. LaBelle went to work on her new album in 2003 and by 2004, LaBelle and Def Jam released Timeless Journey.
Fueled by the release of LaBelle's first hit single in seven years, "New Day", the album eventually topped the pop and R&B charts reaching number 18 on the former and number 5 on the latter. However, LaBelle and Def Jam fell into problems immediately after its release. Shortly after releasing 2005's Timeless Journey, LaBelle told reporters that she was "unceremoniously" kicked out of the label by Reid. After a public spat, Reid renegotiated a new contract with LaBelle in 2007 releasing a Christmas album. Though the album did go gold, it did receive some popularity. Five years later, the ballad "2 Steps Away", co-written by LaBelle and friend Denise Rich, was featured on Dancing with the Stars. The success of the song eventually helped it reach Billboard's Digital Singles chart, her first charted single on that chart. "New Day" topped the Billboard Hot Dance Songs chart in 2004.