В японских хрониках фигурируют варвары мисихасэ, ради изгнания которых с острова Хонсю на север в 7 веке ненадолго объединились даже злейшие враги ямато и эмиси. В китайских хрониках примерно тогда же упоминаются цзилями - это созвучно с "гиляки", устаревшим названием нивхов. В преданиях айнов фигурируют тонцы - воинственный народ, живший до них ещё севернее. Ну а науке известна "охотская культура", или скорее более широкое понятие - "охотская историко-культурная общность", сложившаяся на побережьях между Хоккайдо и Камчаткой около 3000 лет назад. Вот её артефакты в музее Южно-Сахалинска:

Однако ещё несколько сухопутных "мостов" ледниковый период построил на юге. По ним совсем другие люди разошлись из Азии в Австралию, Индонезию и на Японские острова. Японцы с их вечной тягой к эстетике дали всем эпохам своей истории названия, и древнейшей из таковых стала эпоха Дзёмон. Императорские хронисты вряд ли знали её "дно", а современная наука нащупала на "глубине" в 13 тысяч лет. Конец этому первородному хаосу положили ещё одни выходцы с Алтая, общие предки корейцев и японцев, на материке построившие государство Пуё, а на островах открывшие эпоху Яёй. Они обосновались на острове Кюсю, привезя с собой земледелие, торговлю и простейшую фортификацию. На островах пришельцы столкнулись с эмиси, дословно "волосатыми людьми", по нашему говоря - варварами.
Японский варвар был бородат, ясноглаз, зубаст, татуирован и дико свиреп, словом - от античного варвара отличался не сильно. Потомками этих варваров остались айны - пожалуй, самый загадочный народ Евразии, так как наука не знает для них даже приблизительной родни ни по языку, ни по внешнему виду. Японские учёные считают, что бородачи пришли сюда из Сибири и являются потомками её древнейших жителей, европейские учёные же искали айнских предков среди аборигенов Тайваня и Южного Китая: якобы, в незапамятные времена одни ушли на юг, в Индонезию и Австралию, другие на север, положив начало культуре Дзёмон, а все связующие звенья давным-давно растворились в культурных слоях. Как бы то ни было, яёй и эмиси начали воевать буквально с первой встречи, и именно в войнах с айнами сформировалась Япония, начавшаяся с государства Ямато. Да и айнской крови в японцах немало - всё же внешне они даже не совсем монголоиды. Самураи по своему происхождению - не рыцари, а служилые казаки, владевшие всей полнотой власти в лихом пограничье в обмен на его охрану.
Первые века айны были для японцев превосходящим противником, но мало-помалу колонизаторы переняли их военное искусство и начали понемногу брать верх. Борьба шла тяжело, и думаю, не будь японцы заперты морем, они бы трижды послали дикарей ко всем чертям и отступились. В период своего расцвета в 7 веке Ямато контролировало Кюсю, Сикоку и только южную половину Хонсю. Лишь в 11 веке японцы полностью овладели своим крупнейшим островом. Айны отступили на Хоккайдо, в те времена остров Эдзо, за который Япония плотно взялась лишь спустя несколько веков. К тому времени самурай был безусловно сильнее эмиси, и айнам пришлось отступать ещё дальше на север - то есть, на Курилы и Сахалин.
Вещи средневековых айнов в том же музее:

К 17 веку Сахалин стал землёй двух народов, живших по всей его территории, но преимущественно - на противоположных концах. На Северном Сахалине - нивхи, наследники охотской культуры, те самые "не уехавшие индейцы", жившие как типичный малый сибирский народ:

На Южном Сахалине - айны, в боях взрастившие японцев и не похожие ни на кого во всём мире ни языком, ни видом, ни культурой.

Какие-то народы порой проникали в этот странный мирок и с запада, из рыбного устья Амура. На Северном Сахалине помимо нивхов есть эвенки и ороки (уйльта) - один из близкородственных народов Приамурья. На Татарском проливе известны остатки крепостей 12-13 веков, - Ако у Александровска-Сахалинского и Сирануси на мысе Крильон. Это были заморские колонии то ли монголов, то ли, и скорее - чжурчжэней (маньчжур), чьё государство монголы стёрли с лица Земли. По праву маньчжурского наследия в 17-19 веках Сахалин считал своей территорией Китай, хотя нога китайца не ступала на остров, скорее всего, никогда.
Первым иноземцем, увидевшим Сахалин, достоверно считается и вовсе Маартин Гарретсен де Фриз, голландский мореплаватель, добравшийся сюда в 1643 году из Индонезии. Год спустя Карафуто, как назвали этот берег японцы, исследовал самурай Мураками Хиронори из клана Мацумаэ, с 1605 года правившего покорённым Хоккайдо. В том же 1644-м землепроходец Василий Поярков из далёкого Кашина зазимовал в устье Амура, и узнал от тамошних гиляков, что их родня живёт за морем, на большом острове. Самого острова Василий Данилович не увидел, но в русской историографии остался его первооткрывателем. Впервые же русского человека сахалинские айны и нивхи увидели в 1746 году, а в 1790 Сирануси возродилась как японская фактория в будущей Карафуто. Из того же музея - японская фуна и русский коч: