A la base, La Légende de Despereaux ne devait pas être réalisé par Sam Fell et Robert Stevenhagen, mais par le Français Sylvain Chomet (Les Triplettes de Belleville), un temps attaché au projet.
Rares sont les récits pour enfants qui s'imposent comme des classiques dès leur sortie en librairie. C'est pourtant ce qui est arrivé à Kate DiCamillo, l'auteur de La Légende de Despereaux, en 2003, lorsque son roman s'est directement hissé en tête des ventes, et qu'il est resté 96 semaines sur les listes du New York Times.
Selon qu'ils voient le film en VO ou en VF, les spectateurs de La Légende de Despereaux auront droit à une narratrice (Sigourney Weaver) ou à un narrateur (André Dussollier).
Pour créer la ville de Dor, grise et couvertes par d'épais nuages, l'équipe technique de La Légende de Despereaux s'est inspirée de Bruxelles, ou de villes d'Italie et des Balkans.
L'un des objectifs des réalisateurs a été l'immersion totale du spectateur dans l'action : "Lorsque nous tournions un plan avec les souris, nous essayions de nous faire aussi petits qu'elles et de nous imaginer dans la peau d'un de ces rongeurs en train de filmer ses congénères avec une minuscule caméra", explique le directeur de la photo Brad Blackbourn.
Etape clé de la fabrication d'un film d'animation, le stroyboard a ici permis d'assurer l'unité thématique et artistique du film, la cohérence de son histoire complexe (où s'entrecroisent quatre lignes narratives), mais, surtout, de raccourcir de plusieurs mois la phase de développement. Une économie non-négligeable, en regard du budget modeste du film (60 millions de dollars).
"Nous avons passé beaucoup de temps avec nos animateurs pour trouver un style relativement discret, mais assez parlant pour permettre au spectateur de comprendre ce qui se passe dans la tête de nos héros", explique le co-réalisateur Sam Fell.
L'image numérique étant "aussi lisse et satinée que la peinture au pistolet", les producteurs, désireux de donner au film la texture visuelle dense et organique des illustrations des contes de fées, ont été chercher leur inspiration du côté de peintres flamands tels que Vermeer ou Breughel.
Si La Légende de Despereaux est le premier long métrage réalisé par Robert Stevenhagen, c'est en revanche le troisième de Sam Fell, qui quitte pour l'occasion les studios Aardman, pour le compte de qui il avait co-réalisés Les Nouvelles Aventures de Wallace et Gromit et Souris City.