After the release of her second studio album, Jamelia took a break from her career to give birth to her second daughter Tiani. Whilst she was pregnant she started writing new material but due to her new-found happiness she found the process frustrating: "When I first tried to write, I was five months pregnant and every song was either rubbish or insincere. I thought I needed to write another Thank You, but I was so sickeningly happy, I couldn't write anything with any strong emotion." It was not until after she gave birth that she was able to rediscover her song writing skills and start laying down the foundations for her third album. Eager to continue her growth as an artist, Jamelia was determined to continue making music that reflected her personality and musical outlook: "My whole aim was to do something different. I do not believe in giving people something that they have already heard from me. We know what worked the last time (on Thank You) but I think changing and reinventing yourself is the way forward."
The album is named Walk with Me as a tribute to the journey which she has taken over the course of her career: "I just feel like my life and my career has been a journey and I’ve always felt that I’ve been lucky enough to have people just be there for me. It’s also an invitation for anyone who has never bought a Jamelia record to have a listen to it."
Upon its release, the album entered the UK Top 75 albums chart at number 20 before dropping to number 44 the following week and quickly falling off the album chart. However, in January 2007 the album witnessed a resurgence when it re-entered the top 75 chart at number fifty-one, and climbed again to number 45 the following week. As of September 2007, Walk with Me has sold 107,000 copies and has been certified as Gold. The album has also reached Gold status in Poland.