La naissance du projet est à mettre en parallèle avec le désir de Mohamed Hamidi de faire un road-movie à travers la France. Le metteur en scène explique en effet qu'il connait bien les campagnes du pays parce qu'à 17 ans il était animateur de colonies. Par ailleurs, le comédien Fatsah Bouyahmed qu'il connait depuis 10 ans lui avait parlé de l'un de ses oncles passionné d’agronomie et qui lui demandait régulièrement des informations sur le Salon de l’Agriculture qu’il aurait adoré visiter. Mohamed Hamidi confie également qu'il a été marqué par La Vache et le prisonnier ainsi que les road movies Little Miss Sunshine et Une histoire vraie. De ces trois facteurs est né La Vache.
Contrairement à ce que l'on pourrait penser, la vache est un animal très cinématographique ! Hormis les documentaires agricoles lui étant consacrés (Bovines) et les dessins animés comprenant un personnage animé de ce type (La Ferme se rebelle), nous pouvons par exemple citer les films El Chino, La Vache et le Président ou encore La Vache et le prisonnier qui possèdent tous les trois une intrigue dans laquelle une vache est au centre.
Mohamed Hamidi retrouve Fatsah Bouyahmed qui jouait déjà dans Né quelque part, le dernier film du réalisateur avant La Vache. Le choix de cet acteur a été immédiat d'une part pour sa capacité à véhiculer à la fois de l’humour, de la poésie et de la sincérité mais aussi parce qu'il n'est pas connu. Ainsi, le spectateur lambda a vraiment l’impression que ce petit paysan sort du bled avec sa vache.
Pendant 3 ou 4 ans, Mohamed Hamidi s'est rendu régulièrement au Salon de l’Agriculture où il a vu des centaines de vaches. Son critère dans le choix de Jacqueline était le suivant : l'animal devait absolument être marron pour être crédible en vache algérienne. Le réalisateur se rappelle :
"La première que j’ai retenue était une Jersiaise, mais le duo qu’elle formait avec Fatsah ne marchait pas. Elle était un peu trop petite. Ensuite, quand j’ai appris qu’il y avait un élevage de Tarentaises au Maroc, je suis allé les voir et je les ai trouvées très jolies, plus grosses, plus brunes et de bonne taille. Du coup, on a fait un casting à l’envers. J’ai d’abord choisir une belle Tarentaise au Maroc et, ensuite, j’ai cherché son sosie en France. J’ai dû en voir au moins trois cents dans les Alpes ! Les deux sélectionnées sont ensuite parties chez Pierre Cadéac, un dresseur d’animaux pour le cinéma installé à Fontainebleau. C’est là que Fatsah et Jacqueline ont fait connaissance. Pendant tout ce temps, la Jacqueline marocaine avait été mise à l’abri et engraissée. Souad Lamriki, la productrice de cinéma marocaine, l’avait confiée à un jeune garçon, Icham, pour la soigner et, en quelque sorte, l’apprivoiser. Il en est devenu dingue. On a décidé de la lui offrir en lui faisant la surprise le dernier jour de tournage. Il était fou de joie."
Comme Mohamed Hamidi ne pouvait ni emmener une vache française au Maroc (où la partie qui se déroule au bled algérien a été tournée), ni une vache marocaine en France, l'équipe a dû choisir trois vaches identiques, une dans chaque pays et une doublure au cas où…
Mohamed Hamidi voulait que La Vache soit une sorte de fable possédant un aspect politique induit et non démontré. Le réalisateur a cherché, via cette histoire, à montrer que les individus, d’où qu’ils viennent, peuvent cohabiter et partager des choses malgré les différences de culture, de statut social ou de religion. Une portée très en phase avec notre époque d'après lui.
Fatsah Bouyahmed et Jamel Debbouze se connaissent depuis longtemps puisque le premier explique que leur première collaboration remonte à 2006. Il s'agissait d'un sketch pour la radio où il jouait le frère de Zidane au bled et Jamel l'interviewait. Sur le tournage de La Vache, les deux comédiens ont donc forcément beaucoup improvisé.
L'idée d'appeler la vache Jacqueline vient du comédien Fatsah Bouyahmed qui se souvient : "À l’époque du téléphone fixe, je donnais le numéro de la maison et mon père se plaignait car, pour lui, le téléphone ne servait qu’à communiquer avec l’Algérie. Si on parlait plus d’une minute, il intervenait : « Attention, peut-être que l’Algérie nous appelle ! ». Quand des filles téléphonaient, mes parents ne retenaient jamais leurs prénoms. Alors, mon père disait « C’est encore une Jacqueline ». Pour lui, cela signifiait : une jeune fille française. Quand Mohamed a dit qu’il cherchait un nom pour la vache, j’ai proposé : « Jacqueline ». Et il a été d’accord."