Au Paléolithique, la tribu des Ulam connaît l'usage du feu et sait le conserver mais ne sait pas le produire. Les membres de la tribu des Wagabou envahissent le territoire des Ulam et une bataille éclate. Les Wagabou sont représentés comme des sauvages proches de l'animalité, couverts de poils, dont rien n'indique qu'ils maîtrisent un outillage avancé ou le feu, et dont la langue est à l'évidence très rudimentaire. Malgré tout, ce sont eux qui gagnent grâce à l'avantage du nombre, leur force brutale et leurs ruses stratégiques. Une poignée d'Ulam réussit à s'enfuir, en laissant en chemin les blessés. Le gardien du foyer s'enfuit lui aussi avec un peu du feu (le reste a été volé par les Wagabou), mais au bout du compte il l'éteint par hasard, au moment même où un membre retrouve les survivants de la tribu. Sans feu, les voilà condamnés à mourir de froid et de faim. Les Ulam ne veulent pas revenir au cannibalisme et ils décident d'envoyer trois d'entre eux, Naoh (Everett McGill), Amoukar (Ron Perlman) et Gaw (Nameer El-Kadi), à la recherche du feu, recherche pleine de danger. Au cours de leur voyage, ils rencontreront plusieurs espèces de bêtes sauvages, dont des tigres à dent de sabre, ainsi que d'autres espèces primitives d'êtres humains.
Finalement, dans leur exploration, le trio des Ulam entre dans le territoire des Kzamm, une tribu qui ne dédaigne pas de capturer des membres de la tribu des Ivaka pour les manger. Malgré leur inculture et leur brutalité, les Kzamm sont passés maîtres dans l'art de produire le feu. Naoh réussit à le leur voler, mais il est blessé en se battant contre deux d'entre eux. Il rejoint Gaw et Amoukar. Une jeune femme appelée Ika (Rae Dawn Chong), une prisonnière Ivaka qui s'est enfuie avec Naoh, les rejoint, cherchant leur protection.
Un jour, Ika se rend compte qu'elle est près de chez elle. Elle essaie de persuader les trois Ulam de l'accompagner, mais l'absence d'une langue commune ou une méfiance instinctive les retient en arrière. Quand Ika les quitte le matin suivant, Naoh se sent très troublé car il ne peut s’empêcher de penser à elle. Il revient en arrière, suivi de Gaw et d'Amoukar malgré leur réticence. Naoh quitte les autres pour aller en éclaireur dans le village mais est pris dans une embuscade par les Ivaka.
Au début, on lui fait subir des brimades et plusieurs formes d'humiliation, mais finalement les Ivaka l'acceptent et lui montrent leurs techniques. Leur tribu est la plus avancée qui nous soit montrée. Ils sont arrivés à l'étape de l'art (peinture sur le corps, cabanes, ornements, poterie primitive) et ce qui est plus important, ils maîtrisent la production du feu. Quand on apprend à Naoh comment l'allumer, il se sent transporté de joie ; sa vie est changée pour toujours.
Inquiets, Gaw et Amoukar vont à la recherche de Naoh et se font capturer eux aussi. Pendant les épreuves qu'on leur fait subir, ils se rendent compte à leur stupéfaction qu'un de ceux qui y participent est Naoh, qu'au départ ils n'avaient pas reconnu puisque son corps est maintenant couvert de peinture comme les Ivaka. Pendant la nuit Gaw et Amoukar s'enfuient, en assommant Naoh pour l'emmener avec eux. Se rendant compte qu'elle aime Naoh, Ika suit le trio et l'aide à s'enfuir.
Sur le chemin du retour, le quatuor doit se battre contre un ours et un groupe de renégats qui faisaient partie autrefois de la tribu des Ulam. Gaw est sérieusement blessé dans sa lutte contre l'animal, mais il réussit à s'enfuir. Les trois autres membres du groupe le retrouvent et Amoukar le porte sur ses épaules. Lorsque la bataille s'engage avec les Ulam renégats, le groupe utilise plusieurs propulseurs de sagaies volés aux Ivaka et mettent ainsi en fuite leurs ennemis, ce qui montre l'avantage qu'il y a à maîtriser les nouvelles technologies.
Alors qu'ils sont sur le point de rejoindre la tribu des Ulam, celui qui était chargé de porter le feu tombe à l'eau, et le feu s'éteint. Naoh essaie d'en allumer un nouveau en utilisant quelques brindilles, des excréments et des herbes sèches. Plusieurs essais échouent, mais Ika prend les choses en main, en frottant soigneusement ensemble les brindilles sèches. Dès qu'une petite braise est allumée, la tribu se sent tellement submergée de joie qu'elle reste silencieuse. Finalement, Ika et Naoh découvrent qu'Ika est enceinte de leur enfant. Naoh caresse le ventre d'Ika en regardant la couleur brillante de la lune, laissant les spectateurs espérer qu'ils auront peut-être une postérité et contempler l'avenir du développement humain grâce à l'aide conjointe de la science et de la technologie.
