Николай Слюнин, доктор медицины и участник Охотско-Камчатской горной экспедиции оставил описание Тауйска, каким он его увидел в конце XIX века. Тогда Тауйск состоял из 19 домов, 23 летних юрт и 30 хозяйственных построек "с опрятно содержимою церковью". Между тем, он в своей работе приводит крайне любопытное предание о появлении здесь первых русских поселенцев. Обычно, основание села приписывают землепроходцу Михаилу Стадухину, который поставил в устье Тауя острожек в 1653 году. Записанное Слюниным предание говорит о том, что первыми русскими поселенцами стали не стадухинцы, а казаки с реки Амур.
"Тауйск, по официальным данным, населен якутами, (16 семей), правда жители его были переселены сюда из Якутска и Томской губернии, но судя по теперешним чертам лица, это были скорее русские, женатые на якутках, племенные черты которых лучше сохраняются и резче передаются по наследству, как в этом мы не раз убеждались при изучении таких смешанных семей. Кроме того, здесь между жителями еще сохранилось предание, из которого видно, что после разорения какого-то города на Амуре (Албазин?) несколько казаков бежали в Удской острог, а другие отсюда поплыли на кочах и в здешней бухте заштилили целую неделю. Считая кого-нибудь виновным в этом несчастии, они бросили жребий, но он ни на кого не выпадал в течении трех раз; тогда бросили жребий на бывший у них образ Покрова пресвятой Богородицы, и когда он выпал, пришедшие люди поставили крест, к которому прикрепили икону с надписью: "да просвятится место сие". Тогда в этом месте обитала "нехристь", (то есть коряки), икона долгое время оставалась на кресте с оградой, и только в последствии приехавшие из Охотска священники порешили построить на этом месте церковь. Последняя сгорела, но икона осталась и теперь находится в новой церкви. Вышеприведенное предание, помимо антропологических признаков, также указывает на русское происхождение первых жителей Тауйска, которые впоследствии сильно смешались с якутами и тунгусами и приобрели некоторые манеры от американских китобоев."
Конечно, ко времени появления русских на Тауе никаких коряков здесь уже не было. Скорее всего под "нехристью" понимались местные тунгусы. Во время русско-маньчжурских войн XVII в. за обладание Приамурьем известны три большие осады казачьих крепостей. Ерофей Хабаров успешно пересидел осаду маньчжуров в Ачанском остроге в 1652 г. Однако потом казаки все равно бросили острог и ушли вверх по Амуру.
Дважды осаждалась крепость Албазин в 1685 и в 1686 году. Но к этому времени Тауйск уже существовал и числился в списках ясачных зимовий. В 1655 году Онуфрий Степанов отбил приступ превосходящего числом маньчжурского войска в Кумарском остроге на правом берегу Амура (ныне в провинции Хэйлунцзян, КНР). Тем не менее, через три года объединенное войско, куда входили маньчжуры, корейцы,тунгусы и дауры, разбило отряд Степанова у устья р. Сунгари, а сам он погиб вместе с большей частью своих товарищей. Не всех русских убили в сражении, достоверно известно, что некоторым удалось спастись. Возможно, кто-то из казаков отряда Онуфрия Степанова потом оказался в Удском остроге (ныне север Хабаровского края), а затем и в Тауйске.
Любопытно, что в первом сборнике русского исторического фольклора "Древние Российские стихотворения, собранные Киршею Даниловым" (изданном в начале XIX в) есть и сказание об отражении осады Кумарского острога казаками Степанова: "Во сибирской во украине, во Доурской стороне..".