Philippe de Chauveron a débuté seul l'écriture du scénario, il y a un peu plus de deux ans, avec le désir de faire une comédie de situation dans l'esprit de celles des années 80 qui se concentrerait sur trois ou quatre personnages seulement. Et puis lui est venue l'idée de mettre en scène deux flics obligés de travailler ensemble alors qu'une histoire d'amour met une ambiance explosive entre eux.
Jean Dujardin explique les raisons pour lesquelles il a accepté de jouer dans L'Amour aux trousses : "C'est un film générationnel, il y avait un esprit de "team" qui me plaisait, et j'avais envie de tourner avec Pascal Elbé. Je pensais - et ça s'est vérifié sur le tournage -, que notre duo marcherait bien, qu'on aurait le même rythme. Et puis j'aimais les deux histoires parallèles : l'excuse de l'amitié, le côté "polar" et le duo "à trois". Intuitivement, je savais que j'allais pouvoir retrouver avec Pascal le même esprit et le même genre de complicité et de mécanique rapide bien huilée qu'avec Clovis Cornillac dans Brice de Nice ou Alex dans "Un gars, une fille". Pour tout dire, quand je lis un scénario, je m'intéresse d'abord à l'histoire et ensuite au personnage."
L'Amour aux trousses marque les retrouvailles de Philippe de Chauveron avec Pascal Elbé, acteur qu'il avait dirigé dans la comédie Les Parasites.
Ce qui a tout de suite plu à Pascal Elbé à la lecture du scénario, c'est sa construction. "Une construction comme j'aime, explique-t-il, où le spectateur peut se projeter, un peu en référence au cinéma de Francis Veber : jubilatoire à voir. En plus, j'ai ri dès les premières pages. En me disant aussi parfois "et si moi je me retrouvais dans cette situation, qu'est-ce que je ferais ?" (...) J'aime les films qui mettent en scène des personnages en situation de doute, de dilemme. Or les trois personnages de L'Amour aux trousses sont partagés entre deux sentiments contradictoires : avouer ou ne pas avouer, dire ou ne pas dire, pardonner ou accepter... Sachant qu'à la base, tout le monde a trompé tout le monde !"
Le tandem comique Jean Dujardin / Pascal Elbé n'est pas le premier à avoir succombé au charme de l'actrice italienne Caterina Murino. Avant eux, ce sont les comédiens Jean Reno et Christian Clavier qui ont été séduits par la belle dans L'Enquête corse. Caterina Murino poursuivra sa conquête du territoire français en partageant, aux côtés de la troupe du Plendid, l'affiche des Bronzés 3 : amis pour la vie.
Caterina Murino a failli ne pas faire partie de l'aventure. Philippe de Chauveron était en effet très sceptique quant à sa participation au film, la trouvant "trop jolie". A la première rencontre, il est finalement revenu sur son jugement. La belle se souvient : "On a fait des essais et... il m'a offert le rôle. Après, je n'ai plus eu qu'à travailler mon français qui... disons, avait encore besoin de progresser sur les intentions que nécessitent des dialogues comme ceux-là, du tac-au-tac."