Фильм родился из презентационной короткометражки «Raiders of the Stone Ring» Дэйва Аллена. Столкнувшись с многочисленными трудностями при развитии короткометражки в полный метр, Аллен переписал сценарий. Произошло это, когда стало известно, что компания Disney работает над фильмом «Остров на вершине мира» (Роберт Стивенсон, 1974) с аналогичным сюжетом. Годом позже Аллен и эксперт по спецэффектам Рэндолл Уильям Кук приступили к работе над первым вариантом сценария «Первобытных», но вскоре Кук стал аниматором в фантастическом фильме Майкла Рэя «Лазерный взрыв» (1978), а Аллен предложил свой проект продюсеру Чарльзу Бэнду. Тому идея понравилась, и он согласился стать продюсером будущего фильма, выход которого вначале запланировали на 1980 год, о чём ежеквартальный журнал Cinefantastique проинформировал читателей в обширной статье в зимнем выпуске 1978 года. К сожалению, проект оказался затратным, так что оставался у Бэнда только в планах на протяжении всех 1980-х гг. Финансирование нашли только в 1994 году. На анимацию отвели два года и запланировали премьеру на 1996 год, но у Бэнда начались проблемы, Аллен заболел и умер, и проект положили на полку. В 2018 году Бэнд нашёл $40 000 на проект, и работа над фильмом наконец-то завершилась в конце 2022 года.
Эксперты по спецэффектам, включая Криса Эндикотта, после выхода фильма на экраны годами хранили у себя использовавшиеся в покадровой анимации пластилиновые фигурки аборигенов.
Было утеряно 5% оригинальных негативов. На рабочей фильмокопии утерянный материал обнаружился, но на 35-мм плёнке было столько царапин и других дефектов, что многое пришлось восстанавливать до качества соответствующего уровня.
Было смонтировано две версии фильма – одна для широкой публики, а другая, режиссёрская, для домашней коллекции Аллена. Она на 7 минут длиннее прокатной версии, в ней есть сцены, отсутствующие в версии для широкой публики.