Recording for the album began in 1998, when Dido officially signed a record deal with Arista Records. As well as recording ten new tracks, Dido took two previously recorded tracks from her demo collection, Odds & Ends, and used them for the album, with "Take My Hand" appearing in its original form, and "Sweet Eyed Baby" being remixed to create "Don't Think of Me". During recording for the album, a deal to release the album in the United States was finalised, however, a deal to secure European sales of the album was not completed, thus meaning that when the album was released in June 1999, it was released exclusively in America. Prior to the album's release, a promotional sampler titled The Highbury Fields EP was issued to radio stations, featuring four tracks from the album, and "Worthless", another track from the demo collection Odds & Ends.
The album's first single, "Here with Me", was released prior to the album in the United States in May 1999, peaking at number 89 on the Billboard Hot 100, and subsequently becoming the theme music for the popular American TV series Roswell. The song was released worldwide on 3 February 2001, peaking at number four on the UK Singles Chart and number ten in Portugal and Greece, whilst also appearing inside the Top 40 in France and New Zealand.
In an attempt to boost album sales, a second single, "Don't Think of Me", was released on 19 February 2000, but did not fare as well as expected, only peaking at number 35 on the Hot Adult Top 40 Tracks chart.
"Thank You" was released as the second European single in May 2001, peaking at number three in the United Kingdom and reaching the Top 40 in Germany, France and Italy.
The album's third European single, "Hunter", was released in September 2001, reaching the Top 20 on the UK Singles Chart, and achieving Top 10 success in Portugal and Greece.
A fourth single, "All You Want", was released in December 2001, but was ineligible to chart due to only being released as a 3" mini-single. Some of the album tracks were later licenced for use in television programmes, with "My Life" appearing in an episode of the drama series Angel Eyes, as well as alongside "My Life", "Honestly OK" and "Thank You" in several episodes of the Warner Bros. show Popular. The hit song "Here With Me" was the main theme of the TV show Roswell
Upon release, No Angel entered the Top Heatseekers chart at number 50 on 24 July 1999, with sales of less than 20,000 copies. However, success was soon on the cards, when American rapper Eminem took the album track "Thank You" and remixed it for his song "Stan", which was released on 9 December 2000 as the third single from his third album The Marshall Mathers LP. "Stan" used both the beat and hook from "Thank You", and featured Dido on vocals as a way of thanks for the use of her track. Dido also appeared in the video for "Stan", as the pregnant girlfriend of one of Eminem's fans (Stanley). "Stan" peaked at #51 on the Billboard Hot 100, and subsequently created interest for Thank You, which was released as the album's third single on 12 December 2000. On 13 December 2000, the album officially entered the Billboard Hot 200, where it peaked at number four. On 14 December 2000, "Stan" was released in both the United Kingdom and Australia, and subsequently peaked at number one in both countries. Hours later, due to the success of "Stan", the deal for No Angel to be sold in European countries was finalised.
The album was released in Europe on 13 October 2000, with the same tracklisting as the original American issue, with the exception of the addition of the music videos for "Thank You" and "Here with Me", despite "Thank You" not being released a single in Europe at the time, and "Stan", which appeared as a bonus track on most European editions of the album. By the time of release in Europe, the album had sold over 1 million copies in the United States, and had been certified Platinum there. Three weeks after the album's release in Europe, a Japanese issue was released, featuring two bonus tracks that had previously appeared on Dido's demo collection, Odds & Ends, titled "Worthless" and "Me".
No Angel became one of the best selling albums of 2001 throughout the world, being named the biggest selling album of 2001 in the United Kingdom and the second best seller in Australia, being certified 6× Platinum for sales of over 420,000. The album also reached #5 in Canada. The album won the award for Best Album at the 2002 BRIT Awards, where Dido also won the Best British Female award. In 2006, the album was certified 3× Platinum in Switzerland, selling over 100,000 copies there. "No Angel" was one of the three best-selling albums in 2001, with over 10 million plus sales that year.