Avant que Gwyneth Paltrow n'obtienne le rôle de Johanna, la femme de Charlie Mortdecai interprété par Johnny Depp, Carice Van Houten était pressentie pour le rôle.
Johnny Depp avait déjà tourné avec le réalisateur David Koepp 10 ans auparavant dans le thriller Fenêtre Secrète, où il interprétait un écrivain fraîchement divorcé, qui tentait d'écrire un nouveau roman, mais souffrait malheureusement du "syndrome de la page blanche".
Charlie Mortdecai est une adaptation provenant de la série littéraire éponyme inventée par Kyril Bonfiglioli. Le film de David Koepp a choisi de concentrer l'histoire sur l'un des textes de l'écrivain, Don't Point That Thing At Me, publié en 1972.
David Koepp, scénariste sur l'adaptation du roman de Dan Brown, Anges et Démons, retrouve une nouvelle fois l'acteur Ewan Mcgregor, qui interprétait le rôle de Patrick McKenna face à Tom Hanks. Cette fois, David Koepp n'est plus au scénario mais il dirige l'acteur écossais dans son dernier film Charlie Mortdecai.
Pour être au plus près de la série littéraire de Kyril Bonfiglioli, le tournage de Charlie Mortdecai s'est déroulé en Angleterre. Les scènes extérieures ont été tournées à Greenwich dans l'Old Royal Naval College et les séquences de la bibliothèque au Musée Victoria et Albert, dans le quartier de South Kensington à Londres. Pour finir, la demeure de Charlie Mortdecai dans le film se trouve être à Wrotham Park situé dans la campagne anglaise (Hertfordshire). Cependant, les scènes de l'hôtel du West Hollywood ont été tournées dans les célèbres Studios anglais Pinewood et les plans ayant lieu à l'extérieur du Standard Hotel ont été enregistrées à Los Angeles.
La moustache que porte le personnage de Johnny Depp a été longuement étudiée pour le film, car elle est un élément important qui en dit long sur Charlie Mortdecai et son style vestimentaire toujours impeccable. L'acteur avait tout d'abort dessiné le type de moustache qu'il souhaitait sur une serviette en papier, qui avait été remise au chef maquilleur Joel Harlow. Ce dessin inspira alors trois prototypes de moustache ayant la même forme mais des teintes différentes. C'est finalement la plus claire qui a été sélectionnée. Une fois le modèle déterminé, Joel Harlow a fabriqué une trentaine de moustaches permettant d'en changer entre les prises, celles-ci étant très fragiles.
Doté d'un talent particulier pour la métamorphose, Johnny Depp a souhaité agrémenter le physique de son personnage par un espace entre les dents. Le chef maquilleur Joel Harlow a donc fait créer de fausses dents, mais de peur que Charlie Mortdecai devienne un personnage trop caricatural, le réalisateur a préféré opter pour que les dents de l'acteur soient directement colorées.
Même si Charlie Mortdecai n'est pas un film d'action à proprement parlé, certaines scènes ont tout de même nécessité la présence d'un coordinateur de cascades et non des moindres, puisqu'il s'agit de Rowley Irlam qui a travaillé sur les longs-métrages Thor : Le Monde des ténèbres, Capitaine Phillips, Les Gardiens de la Galaxie, Prometheus, Skyfall ou encore La Légende d'Hercule. Trois séquences ont nécessité sa présence, tout d'abord celle de la course-poursuite à Moscou, puis celle se déroulant à Londres, et enfin celle du combat à l'épée.
Charlie Mortdecai marque les retrouvailles entre Ewan McGregor et Gwyneth Paltrow qui avaient déjà partagé le haut de l'affiche d'Emma l'entremetteuse réalisé en 1997, où l'actrice campait une jolie jeune femme cherchant un mari pour l'une de ses amies.
Lors de la scène de combat à l'épée entre Charlie Mortdecai (Johnny Depp) et Emil (Jonny Pasvolsky), des cascadeurs ont d'abord effectué la scène sous les yeux des deux acteurs, pour qu'ils enregistrent les pas et les mouvements à reproduire. Les deux comédiens se sont ensuite lancés, tout en étant accrochés à des câbles pour garantir leur sécurité.
Gwyneth Paltrow et la chef costumière Ruth Myers se sont retrouvées sur le tournage de Charlie Mortdecai, alors qu'elles avaient déjà collaboré pour Emma l'entremetteuse. Pour le rôle de Johanna Mortdecai, les deux femmes ont imaginé un personnage dont l'élégance pourrait se rapprocher d'une femme comme Grace Kelly. Elles ont pensé à lui établir une garde-robe au style british plutôt classique avec des pièces vintages provenant de la mère de Johanna Mortdecai. Néanmoins, certains vêtements sont plus modernes puisque une robe et un tailleur ont été choisis dans les collections de la styliste Stella McCartney.
Paul Bettany a découvert le projet du film Charlie Mortdecai alors qu'il était sur le tournage de Transcendance en compagnie de Johnny Depp. Après avoir lu la trilogie des Mortdecai écrite par Kyril Bonfiglioli, l'acteur a tout de suite accepté d'être intégré au casting.
Le tableau dont il est question au coeur de l'intrigue de Charlie Mortdecai est censé être une oeuvre Goya. N'ayant évidemment pas la possibilité d'utiliser une véritable oeuvre de l'artiste peintre, deux tableaux ont alors été peints par l'artiste Sally Dray qui s'est inspirée de plusieurs oeuvres de Goya. De plus, celle-ci a réalisé deux fois la même peinture, en cas de dégât suite à la scène de combat entre Charlie Mortdecai et Emil.
Gwyneth Paltrow indique qui lui a été difficile de tourner les scènes où elle doit avoir des haut-le-coeur en raison de la moustache que son mari Charlie Mortdecai vient de se laisser pousser et qui ne lui plaît pas du tout. Elle précise : "Le tournage de ces scènes est sans aucun doute ce que j'ai eu de plus dur à faire au cours de ma carrière : c'était très difficile de rester sérieuse. J'ai dû gâcher une quinzaine de prises !"
Le look de Jock, le personnage incarné par Paul Bettany qui est le valet de Charlie Mortdecai, a été inventé par la chef maquilleuse et coiffeuse Sallie Jaye. Celle-ci a créé une cicatrice des plus impressionnantes sur le visage de l'acteur, qui devait cependant apparaître comme un personnage séduisant, c'est pourquoi, au lieu d'avoir perdu un oeil, la maquilleuse a opté pour une lentille de contact spéciale qui ne lui donne pas une apparence repoussante.
Afin d'incarner avec précision le personnage de Charlie Mortdecai, Johnny Depp est allé chercher du côté des acteurs comiques britanniques dont Sid James (Les 39 marches), Peter Sellers (Docteur Folamour et The Party), Bernard Cribbins (Frenzy et Doctor Who) et Terry-Thomas (Les Héros et Side by Side).