Complete Best was released just a few days before Dion's sold-out concerts in Japan, which were a part of the Taking Chances Tour. The compilation includes "To Love You More," which was originally released in October 1995 and became Céline Dion's biggest hit in Japan, topping the singles chart for 4 weeks and selling almost 1.3 million copies. It also features two other singles exclusive to Japan: "The Power of the Dream" and "Be the Man", as well as many of Dion's other international hits.
The new single, "A World to Believe In" (U.S.A. mix), was included as the first track of the compilation. Recorded as an English-Japanese duet with Yuna Ito, the song was released in January 2008, peaking at number 8 on the Oricon Singles Chart. It was Dion's first appearance on the chart since "To Love You More" (dance mixes) entered in April 1999. The duet wasn't available on Dion's previous album, Taking Chances, which includes the original English solo version of the song.
In October 2008, another greatest hits album was released internationally, titled My Love: Essential Collection. Due to the recent release of Complete Best, this compilation was not released in Japan. However, new unreleased tracks were instead included on the CD single for A World to Believe In: Himiko Fantasia, released in Japan at the same time.
The album was certified gold in March 2008 and has sold 173,100 copies during 2008 in Japan. It debuted at number 3 on the Oricon Albums Chart with 34,223 copies sold. Complete Best is Dion's second best position on this chart, after All the Way… A Decade of Song. The album reached also number 1 on the Oricon Daily Chart. However, it went down to number 6 on the weekly chart in its second week, selling 27,281 copies. The following week, right after the Japanese leg of the Taking Chances Tour, Complete Best jumped from number 6 to number 4 with 34,724 sold. The album topped also the Oricon International Albums Chart for 6 consecutive weeks.