Lenard Fritz Krawinkel raconte la genèse du projet : "Holger Tappe, le producteur, et moi sommes de vieux amis. Je viens de Hanovre, mais je vivais à Zurich quand Holger a créé la société Ambient Entertainment et m'a demandé de revenir à Hanovre pour travailler sur Le Monde fabuleux de Gaya."Holger Tappe précise : "Lenard Fritz Krawinkel sait comment vous donner envie ! Les investisseurs ont tendance à se montrer conservateurs, ne se risquant que dans ce qui a été testé et éprouvé. Il est quasiment impossible de produire des projets novateurs. Il faut aussi se rappeler le climat ambiant à l'époque où nous avons entamé ce projet. La Nouvelle Economie venait juste de s'écrouler !"
Finalement, Holger Tappe et Lenard Fritz Krawinkel ont réussi à trouver 14 bailleurs européens, dont le réputé producteur britannique oscarisé Jeremy Thomas, à qui l'on doit entre autres Le Dernier empereur. Thomas a couvert 20 % des coûts de production, qui se sont élevés à plus de 10 millions d'euros. Mais si le financement provient de sources internationales, tous les éléments visuels du film ont été produits en Allemagne.
Jan Berger, scénariste berlinois, a écrit le scénario du Monde fabuleux de Gaya entre 1999 et 2001. L'intrigue a été développée et affinée lors des huit versions du scénario. Les coscénaristes américains Bob Shaw et Don McEnergy, connus pour leur travail sur Hercule et 1001 pattes, ont révisé la version finale.
Le Monde fabuleux de Gaya est pour ainsi dire le premier film d'animation allemand élaboré en images de synthèse. Les personnes qui y ont travaillé, dont le producteur Holger Tappe, sont pour la plupart diplômées de l'Université des Sciences et des Arts Appliqués de Hanovre. Lors de la phase de production la plus intense, qui a duré deux ans, 75 experts de l'animation par ordinateur travaillaient sur ce projet.
La production a permis aux membres de l'équipe de choisir leur propre domaine de spécialisation. "Ils disaient ce qui les intéressait, nous les laissions démarrer, explique Holger Tappe, et nous pouvions ainsi dire rapidement si ça marchait ou non. Nous avions une équipe de dix spécialistes qui se sont exclusivement occupés de la mise en lumière des séquences pendant les huit derniers mois. Huit personnes ont travaillé seulement sur la modélisation et vingt-deux uniquement sur l'animation."
Les personnages principaux sont souvent vus en gros plans, leurs visages devaient donc être représentés avec un soin particulier. Deux techniques ont été utilisées.
La première consistait à transférer les dessins de travail du personnage et la version de la "bible" - les visages clés de face et de profil - dans un programme 3D. La tête était ensuite modélisée directement selon les dessins. Les modéliseurs commençaient par une ébauche grossière qu'ils affinaient petit à petit en divisant les grandes surfaces en plus petites.
La seconde technique impliquait la réalisation d'une tête de plâtre qui permettait aux concepteurs de vérifier les proportions de la tête plus facilement. Une fois le modèle de plâtre approuvé, ses coordonnées géométriques étaient entrées dans l'ordinateur grâce à un bras numérique 3D. Le "grillage" du futur modèle 3D était ainsi fabriqué à partir du modèle de plâtre avant la numérisation.
Une fois l'image informatique en noir et blanc obtenue, il fallait ajouter la texture et la couleur de la peau et des yeux, les cheveux et toutes les expressions. Les corps des personnages ont été créés selon les mêmes processus.
C'est par le biais du coproducteur britannique Jeremy Thomas que Lenard Fritz Krawinkel et Holger Tappe ont pris contact avec le compositeur Michael Kamen, connu pour avoir travaillé sur les musiques de Robin des Bois, prince des voleurs et Don Juan DeMarco. Intéressé par l'originalité du projet des deux jeunes cinéastes, ce dernier les a rencontrés le 1er mars 2002 à Londres, dans le quartier de Notting Hill, où il vit.
Lenard Fritz Krawinkel raconte : "A l'époque, nous traversions une phase difficile de la production, mais grâce à son enthousiasme, Michael Kamen est rapidement devenu une sorte de mentor - une figure paternelle créative si l'on veut. Ça n'arrive pas très souvent que de grands noms du cinéma s'impliquent autant pour soutenir de jeunes cinéastes. Ils nous a donné le courage de continuer et a joué un rôle très important dans la production. Il s'est mis au travail très vite et a organisé des enregistrements avec 80 musiciens à Londres."
Mais le 18 novembre 2003, Michael Kamen décède brutalement d'une crise cardiaque à Londres. La musique était très avancée, mais elle n'était pas terminée. Son manager de longue date, Robert Urband, a accepté de compléter la musique en respectant la vision de Kamen.