In November 2003, at the age of nineteen, Melua released her first album, Call Off the Search, which reached the top of the United Kingdom album charts and sold 1.8 million copies in its first five months of release.
Në nëntor 2003, në moshën nëntëmbëdhjetë, Melua lëshoi albumin e saj të parë, Call Off the Search, i cili arriti në krye të listës së albumeve të Mbretërisë së Bashkuar dhe shiti 1.8 milion kopje në pesë muajt e parë të lirimit.