|Our Story is the first and only studio album by Milenia. It was initially listed to purchase online in April 2003, but became available at some point in 2005 (specific release date needed). The album contained Promise, produced by Prince, and No Can Do (Remix), which was remixed by Prince (he was not involved in the original version, also included on the album).
The recording dates for Prince's contributions are unknown, but it is likely the tracks were worked on during Milenia's brief stint as background vocalists for Prince in late 2000 or early 2001.
No singles were released from the album, which received a low-key release online as a self-released album. The album was not eligible for the charts.