Le film a été tourné en Virginie, le lieu exact qui a accueilli à l'époque le fort de Jamestown que l'on voit dans le film, quasiment à l'endroit où se sont déroulés les évènements décrits dans Le Nouveau Monde.
Il s'agit de la quatrième collaboration de Terrence Malick avec Jack Fisk, qui fut le chef-décorateur de ses trois films précédents. Pour ceprojet, le décorateur dut notamment reconstruire le Fort James, dans une taille cependant 25% plus petite que l'original.
Le département costumes a créé 500 tenues avec une équipe qui ne comptait que 15 personnes.
Le chef-opérateur Emmanuel Lubezki, nominé à l'Oscar pour ce film, a respecté la décision du réalisateur de tourner au maximum en lumière naturelle, sans aucune source artificielle.
L'acteur Colin Farrell avait 28 ans au moment du tournage, l'âge exact de son personnage John Smith lorsqu'il a débarqué en Amérique du Nord.
Q'orianka Kilcher, 15 ans, incarne le rôle principal de ce film. La vraie Pocahontas avait probablement entre 12 et 15 ans, âge adulte pour les Indiens de l'époque. La production a mis plusieurs mois avant de trouver l'interprète idéale de Pocahontas, à l'issue de castings lancés à travers les Etast-Unis, le Canada puis l'Europe. La jeune comédienne Q'orianka Kilcher, née d'un père péruvien, sait chanter, danser et jouer de la musique.
Si la firme Disney a récemment remis la légende de Pocahontas au goût du jour, Terrence Malick a eu l'idée du Nouveau Monde dans les années 70 et a commencé à en écrire le scénario il y a vingt-cinq ans.
Les premiers immigrants anglais, sur la côte est, furent des aventuriers ou commerçants mandatés par le roi, ainsi que des repris de justice condamnés à l'exil; car le territoire n'avait rien d'un eldorado. Les rigueurs du climat et les tensions avec les Indiens y rendaient la vie très dure. On ne compte pas les expéditions décimées ni les campements disparus en un hiver. En 1603, lors de son accession au trône d'Angleterre, James Stuart (Jacques 1er) entend bien asseoir sa position grâce à la religion anglicane. Les persécutions contre les catholiques et les puritains commencent, et ces derniers, en quête de vie plus conforme à leur croyance, émigrent en masse vers le "Nouveau Monde", constituant le coeur des futures colonies. C'est dans ce contexte que John Smith , en avril 1607, à bord du Susan Constant, arrive dans un territoire qui deviendrait plus tard l'état de Virginie.
Aventurier aguerri, soldat dans plusieurs guerres, capturé en Transylvanie et vendu comme esclave aux Turcs avant qu'il ne réussisse à s'échapper à travers la Russie et la Pologne, John Smith fut enrôlé par la Virginia Company dans un plan de colonisation de la Virginie. Il avait 28 ans et Pocahontas, 11 ou 12 lors de leur rencontre en 1607. Il raconte avoir été "capturé" par une tribu Algonquin à son arrivée à Jamestown. Sur le point d'être battu à mort (en fait, lors d'un rite cérémonial), il aurait été sauvé par une petite fille... Pocahontas. Les deux devinrent amis, et ambassadeurs de leurs camps respectifs, aidant à cultiver une entente cordiale. Mais la situation entre Anglais et Indiens finit par se déteriorer, les visites de Pocahontas se firent plus rares, et en octobre 1609, John Smith fut gravement bléssé dans l'explosion d'un baril de poudre, qui l'obligea à retourner en Angleterre pour se faire soigner. Après un autre aller-retour au nouveau monde, vers la région du Maine, il fut jugé par la Couronne anglaise trop impétueux pour continuer ses voyages, il passa le reste de sa vie à écrire sur ses expériences passées, avant de mourir en 1631, à 51 ans.
John Smith décrit Pocahontas, fille de Powhatan, chef indien, comme une jeune fille joyeuse et vivace, qui avait l'habitude de déambuler nue, et n'hésitait pas à jouer à faire la roue avec les garçons. Elle venait souvent au camp anglais converser avec Smith. A ce que l'on sait, Pocahontas épousa un Indien en 1610, tout en continuant à entretenir des relations fructueuses avec le camp de Jamestown. Ce qui ne l'empêcha pas de se faire capturer par un capitaine anglais avide de rançon. Elle fut emmenée dans le camp d'Henrico, où elle commenca son éducation chrétienne et rencontra celui qui allait devenir son second époux, John Rolfe. Il se marièrent en 1614 après le baptème de Pocahontas, rebaptisée Rebecca. Elle avait 19 ans. Ils s'embarquèrent tout deux sur une expédition en Angleterre destinée à recolter des fonds supplémentaires de la Virginia Company, et impressionner la famille royale avec des récits du Nouveau Monde. Pocahontas retrouva John Smith, qu'elle croyait mort. D'après Smith, elle s'adressa à lui comme à un père, très émue, et regretta qu'il refuse de retourner en Virginie. Touchée par une pneumonie ou la tuberculose, elle eut le temps de donner naissance à un enfant, mais ne survécut pas au voyage du retour. Elle fut enterrée en Angleterre.
Afin d'atteindre à une plus grande véracité historique, la production a engagé un expert de la langue Algonquin pour apprendre la langue à tous les acteurs incarnant des Indiens de Virginie, et traduire de larges portions des dialogues du script en Algonquin. Cette langue est quasiment morte depuis 1780.
Bien que le coût d'un tel procédé ne soit pas considéré comme rentable, Terrence Malick est le premier, depuis Kenneth Branagh avec Hamlet, à tourner un film entièrement avec de la pellicule 65mm. Utilisé notamment pour Oklahoma, West Side Story, Spartacus, Ben-Hur et Blade runner, le procédé consiste en fait à tourner sur des négatifs en 65mm puis à les tirer pour la projection en 70mm. La qualité de l'image et du son ainsi obtenue est à ce jour inégalée. A titre indicatif, le tirage d'une copie 70mm coûte près de 15 000 euros, quand celui d'une copie 35mm (format standard) coûte dix fois moins cher.