В 1944 году в Якутске состоялась встреча Окладникова с крупным американским востоковедом О. Латтимором, советником президента Рузвельта. Тот сопровождал вице-президента США Уоллеса в Москву. При перелете с Аляски они сделали остановку в Якутске. Окладников и Латтимор хорошо знали друг друга по работам, но прежде никогда не встречались. Американский профессор подробно расспрашивал о раскопках в Якутии. Он заинтересовался якутской юртой, которая находилась во дворе краеведческого музея, и Окладников обстоятельно рассказал о камельке, внутреннем убранстве, интерьере юрты. Латтимор, как оказалось, был хорошо знаком с юртами монголов. В двадцатые годы он, чтобы изучить монгольский язык, более двух лет путешествовал по Монголии. Кочевал вместе с аратами — монгольскими пастухами, познакомился с их обычаями и религией. В разговоре он заметил: "Это замечательно, что в трудное военное время не прекращается работа историков Якутии". Для многих американцев это было большой неожиданностью. Им трудно было поверить, что в такое тяжкое для нашей страны время правительство не забывает и об исследовательских раскопках в Заполярье. Во время новых встреч с Окладниковым уже в 60-е годы Латтимор часто вспоминал знакомство и беседы в Якутске.
Многолетние работы в Якутии позволили Алексею Павловичу открыть самые ранние этапы истории огромного края. Позднее обработанные материалы составили три тома "Ленских древностей" и первый том трехтомной "Истории Якутии". В своих работах Окладников проследил прошлое якутского народа с глубочайшей древности — первого появления на этой территории человека — и вплоть до прихода в Якутию русских. В основу его работы были положены не только археологические и этнографические материалы, но и богатейший фольклор якутского народа.
Прошли многие годы, но материалы раскопок Окладникова в Якутии и на Охотском побережье и высказанные им идеи не потеряли своего значения и до настоящего времени. Работы, начатые ученым в этих районах, продолжили его ученики и коллеги — Р.С. Василевский, Н.Н. Диков, Ю.А. Мочанов, С.А. Федосеева и многие другие. С каждым годом все полнее раскрывается древняя культура народов Якутии, Северо-Восточной Азии и сопредельных районов — Аляски, Канады, Гренландии. Огромный район, где развивались древние и самобытные культуры в глубокой древности, обнаруженные впервые Окладниковым, продолжает волновать ученых не только нашей страны, но и зарубежных.
Не только Сибирь увлекла Окладникова своими открытиями. Многие годы ему пришлось работать в Средней Азии, где с его именем связаны удивительные находки, обогатившие советскую и мировую науку.
В начале 1938 года из Ташкента пришло письмо в Институт истории материальной культуры Академии наук, где в то время работал Алексей Павлович. Известный советский ученый, профессор Михаил Евгеньевич Массон — блестящий знаток и исследователь древних культур Средней Азии — ставил вопрос о необходимости исследования каменного века в Узбекистане.
К тому времени благодаря трудам русских ученых-востоковедов академиков Бартольда, Веселовского, археологов Вяткина, Массона, Пампелли, Якубовского, Толстова и других исследователей Средней Азии открылся удивительный мир земледельческих цивилизаций.
На юге Средней Азии у Туркмено-Хорасанских гор были открыты поселения анаусекой культуры. Они представляли собой небольшие деревушки и крупные поселки — многолюдные селения — центры больших и могущественных племен. Анаусцы были земледельцами и скотоводами. Так постепенно начинает развиваться в Средней Азии древнейшая городская цивилизация. Народы Средней Азии принимали на протяжении многих тысяч лет активное участие в исторических процессах. Саки и массагеты попали на страницы "Истории" Геродота, который довольно подробно описал войну массагетской царицы Томарис с тщеславным персидским царем Киром. Горы и долины Средней Азии были свидетелями гибели Кира и торжества Дария, могущества великого македонца — Александра и трагедии Спитамена. Много интереснейших страниц древней истории среднеазиатских племен удалось написать археологам и востоковедам к концу 30-х годов. Но в основном это были памятники, относящиеся к сравнительно позднему времени: наиболее древние анауские племена расселялись на юге Средней Азии около 5 тысяч лет назад. А что было до них? Совершенно очевидно, что древние культуры и государства должны были иметь более ранние этапы, на основе которых и развивалась в последующем среднеазиатская цивилизация. Встал вопрос о поисках каменного века.
Возглавить работы по изучению ранних этапов истории народов Средней Азии было поручено Окладникову. Вместе с ним долгие годы в Средней Азии работала и Запорожская.
Сибирякам было особенно тяжело вначале. Они привыкли работать в условиях Сибири, где главное бедствие — комары, мошка — знаменитый ангарский гнус, дожди и холодная осень. А здесь постоянно мучила жара.
В первый день Массой, отправляя их в разведочный маршрут, выделил на двоих фляжку воды. "Выпьете утром, в обед — зеленого чаю, он хорошо утоляет жажду, и в третий раз — вечером", — предупредил он. Но как можно не пить, если нещадно палит солнце и от песка веет, как от раскаленной русской печи? Уже через час воды не осталось, и весь день, переходя с одного бархана на другой, археологи вспоминали Ангару, ее ледяную живительную воду, от которой сводит скулы и ломит зубы. Стоило закрыть глаза, как слышался шум сосен над головой и плеск воды далекой холодной реки.
Работы по изучению каменного века было решено начать из долины речки Турган-Дарьи, над которой поднимались вершины гор, покрытые белоснежными шапками снега. Отсюда начался долгий и утомительный путь вверх, в горы, где охотникам за дикими козлами издавна были известны таинственные пещеры. Вот в них-то и мог жить древний человек в то время, когда он еще не научился строить искусственные жилища. Предстояло перевалить через Сары Шато. За ним лежала Мачайская долина. Именно там, в местности Каттакурган, директор Сурхан-Дарьинского музея Парфенов нашел несколько обработанных рукой человека камней. Для обследования пещер Мачайской долины и направилась небольшая экспедиция под руководством Окладникова.
Долгих восемь дней карабкались путешественники с проводниками, пастухами из поднебесного кишлака Юкары-Мачай по крутым, извилистым тропам, по узким карнизам над зияющими внизу жерлами пропастей и ущелий.
Временами вверху проносились гонимые ветром тучи.
А чаще пылало и обжигало все вокруг беспощадное среднеазиатское солнце. Изредка путешественники приникали губами к маленькой лужице, стоявшей как прозрачный кристалл в природной сталагмитовой чаще. И снова шли вперед, навстречу новым пещерам, где надеялись найти следы первобытных обитателей этой суровой и вместе с тем невыразимо прекрасной горной стороны, от которой веяло прохладой не тающих летом снежных шапок на могучих вершинах пиков. На высоте двух тысяч метров над уровнем моря зелень арчевников вплотную подступила к вечным снегам высокогорного пояса. Отсюда на сотни и тысячи километров простиралось царство горных козлов и снежных барсов. Выше поднимались только орлы!
Наконец вдали показалось темное отверстие в скале. Это и был таинственный грот Тешик-Таш, "камень с щелью", куда археологов привели на восьмой день скитаний проводники. В нем было светло, просторно и даже сухо, несмотря на прохладу подземелья, столь драгоценную в это жаркое время. Только с потолка в самой середине грота медленно и ритмично падала капля за каплей чистая прозрачная вода.
Там, где падали капли, образовалась ямка глубиной не более двадцати сантиметров, а в ней, на самом деле, лежали кости животных. Кости были раздроблены человеческой рукой. Они давно пожелтели, но еще сохранили твердость. Однако ясно было с первого взгляда, что кости эти не нашего времени, что они лежали в земле не одно тысячелетие, пока их не обнажили капли, падающие с потолка. Самой же замечательной из здешних находок оказался кусок камня, безусловно, обработанный той же человеческой рукой, которая когда-то дробила найденные рядом кости. Он, этот кусок камня, принес археологам не только радость открытия, но и успокоение: теперь, наконец, они знали, что найдено пещерное поселение человека, и притом неожиданно древнего!