Родился 3 октября 1908 года в деревне Константиновщине (Верхняя Лена, Иркутская губерния) ныне Жигаловского района Иркутской области в семье сельского учителя. Русский.
Еще будучи школьником, в летний период он обследовал окрестные места в поисках археологических памятников. Незабываемое ощущение он испытал, найдя недалеко от села черепки глиняной посуды. Это убедило его, что Ленскую тайгу человек заселил давно. Страсть к истории определила его дальнейшую судьбу. В 1925 году после окончания Ангинской средней школы Качугского района поступил в Иркутский педагогический техникум, а в 1929 – на исторический факультет Иркутского пединститута.
В 1929 году Окладников исследовал «писаницы» на скалах у древнего русского села Шишкино на Лене. Первобытный человек тысячи лет назад нанес рисунки животных, птиц, рыб.
Эти открытия имели мировое значение, ибо показали, что не только в Испании, Франции есть подобные шедевры первобытного творчества.
В 1934 году Окладников поступил в аспирантуру при Государственной академии истории материальной культуры (г. Ленинград), которую окончил под руководством П.П. Ефименко в 1938 году, защитив кандидатскую диссертацию на тему: «Неолитические могильники в долине реки Ангары».
В 1936 году ему удалось открыть на берегах Ангары палеолитические поселения с произведениями искусства возрастом в 20 тысяч лет.
В конце 30-х годов он работал в Средней Азии, где в 1938 году в пещере Тешик-Таш (Узбекистан) открыл первое на территории СССР погребение неандертальского мальчика.
С 1938 по 1961 год Окладников являлся сотрудником Ленинградского отделения Института истории материальной культуры. С 1949 по 1953 год был заведующим этого отделения, в последующие годы являлся заведующим сектором палеолита.
После Великой Отечественной войны Алексей Павлович обследовал остатки экспедиции русских полярных мореходов XVII века на острове Фаддея (у северо-восточного побережья полуострова Таймыр, 1945 год); работал в археологических экспедициях в степях Монголии, где также были открыты пещерные росписи. Член КПСС с 1946 года.
В 1947 году Окладникову присуждена степень доктора исторических наук за работу «Очерки по истории Якутии – от палеолита до присоединения к Русскому государству».
Новый период жизни Окладникова был связан с его переездом в 1961 году в Новосибирск.
С 1961 по 1966 год Окладников занимал должности заместителя директора Института экономики и организации промышленного производства СО АН СССР, заведующего Отделом гуманитарных исследований этого института. В 1962 году Алексею Павловичу Окладникову присвоено звание профессора по специальности «Археология», он стал заведующим кафедрой всеобщей истории Новосибирского государственного университета.
После образования в декабре 1966 года Института истории, филологии и философии СО АН СССР Окладников назначен его директором, оставался им до своей кончины 11 октября 1981 года. В Институте истории, филологии и философии СО АН СССР по инициативе академика А.П. Окладникова создан музей истории и культуры народов Сибири и Дальнего Востока. Экспозиции музея иллюстрируют многообразие и преемственность в развитии древних культур Сибири, их взаимодействие с духовными богатствами русского населения края.
Впервые в истории советской археологической науки группа археологов Института истории, филологии и философии СО АН СССР во главе с академиком А.П. Окладниковым приняла участие в совместной советско-американской экспедиции по изучению древних стоянок первобытного человека на Алеутских островах и Аляске.
Титулы А.П. Окладникова: член-корреспондент по Отделению истории с 26 июня 1964 года, академик по Отделению истории с 26 ноября 1968 года, заслуженный деятель науки Якутской АССР (1956), РСФСР (1957), Бурятской АССР (1968), профессор. Дважды лауреат Государственной премии СССР (1950, 1973). Вторая Государственная премия СССР присуждена академику А.П. Окладникову (Институт истории, филологии и философии СО АН СССР) вместе с чл.-корр. АН СССР В.И. Шунковым (Институт истории АН СССР) как главному редактору 5-томной «Истории Сибири с древнейших времен до наших дней» (Л.: Наука, 1968–1969).
Награжден орденом Ленина, тремя другими орденами, а также медалями. Указом Президиума Верховного Совета СССР от 2 октября 1978 года академику Алексею Павловичу Окладникову за большие заслуги в области археологии и исторической науки, в подготовке научных кадров и в связи с 70-летием со дня рождения присвоено звание Героя Социалистического Труда.
Более полувека каждое лето выезжал Окладников в экспедиции для поисков и изучения следов пребывания древнего человека на территории нашей страны. Ему принадлежит честь открытия ряда замечательных памятников далекого прошлого: стоянки и наскальные изображения, открытые и изученные под его руководством на Ангаре, Лене, Колыме, Селенге, Амуре и Уссури, впервые позволили точно и полно представить историю древних обитателей Сибири и Дальнего Востока на протяжении многих тысячелетий.
В последние годы он много сил отдавал изучению стоянки Улалинка близ Горно-Алтайска, которую считал древнейшей в Сибири и на Дальнем Востоке.
Им опубликованы сотни обобщающих исследований по истории первобытного общества и первобытной культуры, по палеолитическому и неолитическому искусству, по истории Сибири, Дальнего Востока и Крайнего Севера с древнейших времен до XVIII века.
На основании результатов многолетних исследований археологических памятников и множества феноменальных открытий выдвинул сенсационную гипотезу о Южной Сибири как одном из центров антропогенеза и новых миграционных потоках древних людей.
Благодаря открытиям стоянок, древних культур в Горном Алтае и Восточной Сибири неожиданно глубокий возраст человечества Сибири датируются Алексеем Павловичем Окладниковым более чем в 1,5 миллиона лет! Правильность многих выводов Окладникова подтверждается исследованиями современных археологов [245, 337, 410, 454, 738, 873, 927, 1126, 1139, 1192].