Dans Votre majesté, on retrouve le trio gagnant qui a fait le succès du film Délire Express : James Franco et Danny McBride en tête du casting, et David Gordon Green derrière la caméra.
Le scénariste Ben Best a l'habitude d'écrire pour Danny McBride, puisqu'il a également travaillé sur The Foot Fist Way et sur la série Eastbound & Down.
Après le succès du thriller Black Swan, dans lequel elle interprétait une danseuse étoile sous pression, Natalie Portman change de registre en s'affichant dans une comédie. L'actrice avoue avoir été séduite par son rôle de dure à cuire : "Elle est très concentrée sur sa quête (...) chaque personne qu'elle rencontre sur son chemin est juste un moyen de plus pour arriver à ses fins", dévoile-t-elle sur son personnage.
Si Danny McBride n'est peut être pas très connu en France, c'est un comique confirmé aux Etats-Unis. Ici, il joue un anti-héros paresseux aimant les jeunes filles, qui est contraint de partir à l'aventure. L'acteur a commencé sa carrière dans un drame romantique (All the Real Girls), déjà devant la caméra de David Gordon Green. En 2006, il fait connaître son registre comique au public américain avec la comédie The Foot Fist Way, puis avec Délire Express (toujours de David Gordon Green). Il retrouve à nouveau ce même réalisateur pour quelques épisodes de la série Eastbound & Down, avant de travailler sur Votre majesté.
Aux Etats-Unis, les bandes-annonces commencent par un carton vert si le film est tous publics, ou rouge s'il ne l'est pas. Il y a, dans Votre majesté, un plan où l'on voit Natalie Portman de dos, ne portant qu'une simple lanière (une sorte de string médiéval), apparaissant dans une bande-annonce à public restreint. Or, ce plan apparait aussi dans la "Green Band Trailer", mais pour ne pas choquer, la lanière a été numériquement changée en un vêtement plus... consistant.
Pendant le tournage, James Franco a fait des allers-retours entre Belfast et New-York pour suivre ses cours à l'Université de Yale où il prépare un doctorat en anglais. Pour les besoins du film, il s'est entraîné pendant neuf mois aux combats à l'épée. Le réalisateur revient sur leur collaboration : "Il nous testait dans les premiers jours pour s'assurer que nous allions être assez gonflés pour lui et nous l'avons poussé jusqu'à la limite."
Le collaborateur habituel de Guillermo del Toro, Mike Elizalde (marionnettiste et spécialiste des effets spéciaux), a travaillé sur les personnages animés du film. Son préféré est le Minotaure nu : "C'était très important pour moi de rendre ce monde aussi tangible que possible. Autant que nous avons eu besoin d'augmenter les effets numériques, j'ai voulu rendre les choses aussi matérielles que possible. Le costume du Minotaure que les types de Spectral Motion ont fait pour nous est phénoménal. Il le rend vraiment convainquant comme animal, à la fois monstre et délinquant sexuel", explique-t-il. Ce costume de Minotaure porté par Brian Steele représentait un peu près l'équivalent de sept parkas portées en plein milieu de l'été...
Danny McBride n'est pas le seul a avoir joué devant la caméra de David Gordon Green. Zooey Deschanel, elle aussi, a déjà tourné avec le metteur en scène dans All the Real Girls. Pour elle, Votre majesté constitue le film le plus "sale" de sa filmographie, mais aussi le plus hilarant.
C'est l'acteur, réalisateur et scénariste Charles Dance qui interprète le rôle du Roi Tallious. Il confie : "C'est l'un des personnages les plus mystérieux que j'ai jamais joué. Il est légèrement sauvage, certainement incompétent et de temps en temps vicieux."
Bien que le film soit écrit par le scénariste Ben Best et l'acteur Danny McBride, les dialogues ont été majoritairement improvisés. Le réalisateur David Gordon Green déclare d'ailleurs qu'aucun script n'a été utilisé sur le plateau. Danny McBride parle de ses inspirations pour le projet : "Notre long-métrage est né des films avec lesquels nous avons grandi, comme Conan le barbare et Le Dragon du lac de feu, tous ces films mélangeant habilement l'action et le fantastique. Nous voulions faire le nôtre, mais en même temps, sans en faire une parodie."
Pour accentuer le comique du film et les anachronismes, le créateur des costumes, Hazel Webb-Crozier, a réalisé des costumes médiévaux inspirés des années 70 et 80 façon David Bowie. Quant à la tenue de Natalie Portman, il a dû la fabriquer sans vrai cuir car l'actrice refusait d'en porter : "J'ai travaillé avec Natalie pour obtenir un ajustement très serré, donnant une apparence de guerrière très sexy qui trompe le téléspectateur parce que ce n'est pas du cuir du tout. Nous y avons ajouté aussi des petits morceaux d'or et nous avons gardé la tenue médiévale", explique-t-il.
Le tournage a eu lieu sur les terres irlandaises, idéales pour le film du fait des mythes et des légendes propres à cet endroit. L'arène forestière de Marteetee a été construite sur une propriété privée juste à l'extérieur de Belfast. Pendant plus de 8 semaines, 15 personnes ont édifié le décor de Marteetee. La place a été construite en utilisant 150 arbres. Un tunnel en bois de 30 mètres a été intégré comme le point d'entrée pour les prisonniers dans l'arène. Enfin, presque 3000 longueurs de saule ont été utilisées pour construire les cages de maille.