Treize ans plus tard, en 1967, Grimault récupère les droits et le négatif du film. Le film sorti en 1953 étant pour lui un faux, il décide de reprendre son film afin de le terminer selon son projet initial. Enfin pas tout à fait, car le temps a fait son œuvre, et Grimault a évolué, ainsi qu’il l’explique dans une interview réalisée par Jean Pierre Pagliano : « Le Roi et l’Oiseau que j’ai sorti longtemps après, est à la fois le même film et un autre film. C’est la même histoire à l’origine mais en même temps qui a bénéficié de tout le drame qu’il a eu autour, et du fait que j’ai eu du recul. Quand j’ai repris mes billes, d’abord je me suis dit : je vais refaire ce film comme je voulais le faire à l’époque. Mais c’était une connerie : de l’eau était passée sous les ponts et je ne voulais pas faire un film rétro.(…) C’est un peu comme un gars qui peint une toile, tant qu’il l’a pas signée, il pense qu’il peut toujours l’améliorer. »

Mais pour mener à bien sa nouvelle entreprise, Grimault doit trouver un financement. Les Américains et les Russes lui font des offres qu’il refuse, car cela impliquerait de délocaliser la production, or le réalisateur veut garder son équipe de base sur place. Finalement, il obtient une aide du CNC qui est complété par Robert Dorfmann et Antenne 2.

De 1977 à 1979, Grimault travaille avec une équipe réduite minutieusement sélectionnée. Tout est déjà en place et avant 1977, Grimault avait préparé son découpage, dessiné et peint les principaux décors des nouvelles scènes.

Fin 1977, de nouveaux et jeunes animateurs rejoignent l’équipe dont Philippe Leclerc qui a réalisé « Les enfants de la pluie » film d’animation sorti en juin 2003. Selon Grimault « le brassage des anciens et des nouveaux s’est avéré merveilleusement harmonieux et profitable pour le film ».

Au final, le cinéaste a coupé 20 minutes du film original (sur 87 minutes) qui ne correspondait pas au film que Prévert et lui avait imaginé. Aujourd’hui le film fait 87 minutes, il a donc repris la moitié du film original mais seulement des séquences très morcelées, ce qui a exigé un travail très minutieux. Prévert, très malade à l’époque, continue à travailler avec Grimault sur cette nouvelle version.

Grimault raconte : « J'allais voir Jacques le plus souvent possible et lui apportais des images du film, des séries de croquis, des décors et, de temps en temps, une idée jaillissait dans la conversation. (…) Même à la fin, se sachant très malade, ce travail était en quelque sorte pour lui une survie, il savait qu'il ne verrait pas le film, mais c'était une revanche qu'il prenait. Quinze jours avant sa disparition, Jacques travaillait encore une dernière fois avec moi. Le plan final où le Robot libère le petit oiseau et écrase la cage a été la dernière scène sur laquelle nous avons travaillé ensemble. »

Au niveau scénaristique, les deux amis procèdent à des améliorations. Ils conservent le premier scénario mais en l’enrichissant de certaines scènes, en rajoutant des nouvelles séquences plus spectaculaires.

Au niveau des personnages, Grimault s’est aperçu que d’autres personnages gagneraient à prendre plus d’importance. « La bergère et le ramoneur sont gentils, attachants, tout ce qui leur arrive nous touche, mais c’est le conflit entre le roi et l’oiseau qui prend progressivement la première place. C’est d’ailleurs la raison du changement de titre. Le Roi et l’oiseau ont pris beaucoup d’importance par rapport au film La bergère et le ramoneur. »

Grimault et Prévert changent le titre évitant ainsi toute confusion avec l’ancienne version et soulignant surtout le fait que Le Roi et l’Oiseau est un nouveau film et non une reconstitution.