Critics gave the album generally positive reviews, praising Cole's interpretations of the covered material, and compared her favorably to contemporary R&B artists.

Co-executive producer David Munk suggested the concept for Leavin' as a way for Natalie Cole to return to R&B through "an intimate, classic soul CD with a small group of sidemen and simple production".

According to Vibe, Cole decided to do a cover album to establish a connection between song and interpreter and between singer and audience" and appeal to "fans yearning for the good old days before they had to hire a sitter to go see a show".

Discussing her dissatisfaction with being labeled a jazz singer and her desire to showcase her versatility, she said that she wanted to "put out some music that we hadn't heard in a long time from anybody, really".

Len Righi of The Morning Call wrote that Cole transformed the song from an "agonizing, brazen lament" into "a funky, Tina Turner-type, rump-shaker.

[7] Richard Harrington of The Washington Post felt that the fourth track, a cover of Shelby Lynne's "Leavin'" (1999), "metaphorically put a little distance between the original R&B diva and the pop star Cole".

[14] The eighth track on the album is a cover of Bonnie Raitt's "Love Letter" (1989),[15] and the following song "The Man with the Child in His Eyes" (1978) was described as an "ethereal" take on the Kate Bush original.

[2] Maura Johnston of Rolling Stone wrote that the original song "5 Minutes Away" was a "rumination on love and life accented by dry horns and capped with a rousing call-and-response".

[16] The tenth track is the second original song "Don't Say Goodnight (It's Time for Love)", written by Cole, Ernie Isley, and Chris Jasper.

[19] To promote the album, Cole was slated to appear on "a number of major morning and late night television programs" to perform "several intimate showcases" of her music.

[21] Director Doug Biro shot the accompanying music video, which features Cole singing with her band in front of a white background.

[22] The song earned Cole a nomination at the 49th Annual Grammy Awards for Best Female R&B Vocal Performance, but she lost to Mary J. Blige for her 2005 single "Be Without You".

[28] People's Ralph Novak, Chuck Arnold, V. R. Peterson, and Monica Rizzo commended Cole's decision to "ditch the evening-gown fare on her new CD" by recording more contemporary songs.

[29] Gugu Mkhabela from News24 awarded the album three out of five stars, describing the material as "pure old school with a modern twist", with Cole providing "a touch of class and some depth to boot".