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 #89 on the Billboard Hot 100, and subsequently becoming the theme music for popular American TV series Roswell. Upon release, the album entered the Top Heatseekers chart at #50 on 24 July 1999, with sales of less than 20,000 copies. 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 #35 on the Hot Adult Top 40 Tracks chart. However, success for No Angel was soon on the cards, when popular American rapper Eminem took the album track "Thank You" and remixed it for his song "Stan", which was released as the third single from his album The Marshall Mathers LP on 9 December 2000. "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 one of Eminem's fans (Stanley) pregnant girlfriend. "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 #4.
On 14 December 2000, "Stan" was released in both the United Kingdom and Australia, and subsequently peaked at #1 in both countries. Hours later, the deal for No Angel, to be sold in European countries was finalised, due to the success of "Stan". The first European single, "Here With Me", was released on 3 February 2001, peaking at #4 on the UK Singles Chart, #10 in Portugal and Greece, and appearing inside the Top 40 in France and New Zealand. 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". "Thank You" was subsequently released as the second European single in May 2001, peaking at #3 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 from the album, "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 "Honestly OK" and "Thank You" in several episodes of the Warner Bros. show Popular. 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 3 best-selling albums in 2001 with a 10 million plus sales that year.