Le film reprend un schéma récurrent chez le réalisateur Francis Veber, celui du « dur » encombré d'un gêneur collant, déjà exploité dans L'Emmerdeur (1973), La Chèvre (1981), Les Compères (1983) et Les Fugitifs (1986).

Il s'agit du seul film français de Francis Veber dont le héros ne porte pas le nom de Perrin ou Pignon, patronymes récurrents dans son œuvre.

Le scénario est basé sur une idée originale de Serge Frydman, adaptée et dialoguée par Francis Veber lui-même.

Le film a été entièrement tourné à Paris du 16 septembre au 24 décembre 2002, dans plus de dix arrondissements différents, notamment rue de Grenelle, rue François 1er, rue Paul-Bert, au bois de Vincennes et place Émile-Goudeau.

La scène où les personnages joués par Gérard Depardieu et Jean Reno traversent un square pour échapper à la police a été tournée à Vincennes, au square Saint-Louis.

Dans une scène, le personnage de Quentin se réfugie dans un cinéma où est projeté le film Ice Age, et se fait arrêter parce qu'il s'assoit pour profiter du film au lieu de continuer à fuir.