Angel-A marque le retour à la réalisation de Luc Besson qui n'avait plus tourner de films depuis Jeanne d'Arc en 1999. Ces dernières années, le cinéaste s'était essentiellement consacré à la production d'oeuvres qui ont connu un grand succès commercial comme les sagas de Taxi et du Transporteur.
Avec Angel-A, l'humoriste Jamel Debbouze effectue, tout comme Besson, son grand retour au cinéma. Depuis Astérix et Obélix : mission Cléopâtre en 2002, le comédien s'était contenté de timides apparitions dans Les Clefs de bagnole et She hate me de Spike Lee.
C'est durant le Festival de Cannes 2005 que Jamel Debbouze a évoqué le projet Angel-A (encore non baptisé à l'époque) en des termes très mystérieux, déclarant au magazine Première qu'il allait tourner "une comédie romantique avec un monstre du cinéma mondial. (...) Je ne peux pas vous en parler. Tout ce que je peux vous dire, c'est que c'est une bombe !"
Luc Besson a longuement entretenu le mystère sur l'actrice principale du film, ce qui a eu pour effet de générer les rumeurs les plus folles concernant l'identité de l'heureuse élue. Parmi les noms qui ont circulé, on retiendra ceux de Sara Forestier, Milla Jovovich et Kate Nauta échappée du Transporteur II.
Mais c'est finalement la belle et méconnue Rie Rasmussen qui a remporté les faveurs du cinéaste. Née en 1978, ce mannequin d'origine danoise est devenue la figure emblématique des marques Victoria Secret et Gucci. Entamant une carrière cinématographique, elle s'est illustrée en 2002 dans Femme fatale de Brian De Palma, puis s'est essayée à la réalisation avec un court métrage intitulé Thinning the herd, présenté au Festival de Cannes 2004 et produit par... EuropaCorp, la société de Luc Besson.
Le tournage, exclusivement parisien, s'est déroulé sur sept semaines durant l'été 2005 dans la plus grande discrétion, et ce malgré le blocage d'un grand nombre de rues et des quais de Seine. Quelque temps avant la sortie du film, on ignorait encore l'histoire et la composition du casting, Luc Besson ne souhaitant révéler qu'un minimum de choses.
S'étant vu refuser l'autorisation de tourner dans l'ambassade américaine à Paris, Luc Besson et son équipe ont été contraints de la recréer complètement.
Du propre aveu de Luc Besson, "certains plans avaient des allures d'opération commando. Il fallait aller très vite, ne faire que deux ou trois prises, poursuit le cinéaste dans une interview accordée au magazine Première. D'autant plus que les conditions météo, soleil-nuage-soleil, ne nous laissaient que des fenêtres de tir très courtes."
Angel-A est le deuxième film de Luc Besson tourné en noir et blanc, le premier étant Le Dernier combat en 1983.