Recording for the album began in 1998 when Mo was signed to Elektra; two singles ("If You Wanna Dance" & "5 Minutes") were released as potential lead singles. However, the lack of proper charting performance from both singles resulted in a postponement for Based on a True Story; both singles would also be subsequently deleted from the album.
By 2001, Mo would later convince Elektra to release "Superwoman" under the "Part II" version featuring Fabolous. Elektra agreed and released the remixed single; the song would go on to peak at number 11 on Billboard Hot 100 and number 4 on Billboard Hot R&B/Hip-Hop Songs, making it Mo's successful single to date. Mo went on to release another single titled, "Gangsta", which failed to match the success of her preceding single.
The album was released on June 26, 2001 to generally favorable reviews. Dan LeRoy of AllMusic gave the album 3/5 stars. He described Mo's voice and musical style in comparison towards Mary J. Blige. Months afterward, the album would go on to attain a Gold certification from the RIAA.