Ермак ввел железную дисциплину в своем войске. За легкие проступки виновных наказывали плетями. Изменников и дезертиров карали смертью: «А кто подумает отойти от них и изменити, не хотя быти, тому по донски указ: насыпав песку в пазуху и посадя в мешок, в воду. И тем у Ермака вси укрепилися». Эта дисциплина соблюдалась на протяжении всего похода.
1 сентября 1581 года у деревянных стен Нижнего Чусовского Городка собрались жители всех окрестных деревень. Звонили колокола, созывая народ на прощальный молебен. В толпе землепашцев, солеваров, лесорубов, охотников здесь и там виднелись суровые лица и боевые доспехи Ермаковых дружинников. Многим из них не суждено было вернуться в родные места из похода в далекую Сибирь. У берега на причале стояли большие лодки-струги, тяжело нагруженные припасами. На их тонких мачтах развевались, трепеща на свежем ветру, знамена и хоругви из тяжелой шитой парчи, маленькие разноцветные флажки, знаки отличия есаулов и сотников.
Но вот прощание окончено. На стенах острожка рявкнули пушки. Весла дружно ударили по воде — и весь караван, под звуки барабанов, литавр и труб, двинулся вверх по Чусовой.
Ермак Тимофеевич долго стоял на корме струга, пристально вглядываясь во все уменьшающиеся очертания Чусовского городка, — последнего русского укрепления на пути в Сибирь. Вот от Городка осталась видна только верхушка церковной колокольни, обитая белой жестью. Наконец, и ее заслонили мохнатые береговые горы.
Сибирский поход начался в очень трудных условиях. Кучум фактически уже приступил к военным действиям (набег Бекбелея Агтакова). Вскоре же после ухода Ермака в Прикамье, которое оставалось слабо защищенным, вторгся подвластный Кучуму пелымский князь Кихек. Он подверг прикамские земли невиданному до сих пор разорению. Кихек, пройдя северным путем по Лозьве и Вишере, в начале сентября осадил Чердынь. Одновременно один из его отрядов, пробравшись малоизвестными тропами, зашел в тыл Ермаку и отрезал его от русских поселений и острогов. Не сумев взять Чердынь, Кихек, опустошая все на своем пути, направился к Соликамску, разграбил и сжег его. Затем он прошел мимо Пыскора и Орла-городка, свернул на Чусовую и выжег по ней многие русские селения. Однако Кихеку не удалось взять ни Сылвенского, ни Чусовского городков. С Чусовой он отправился на восток по следам Ермака. К отрядам Кихека присоединилась и часть коренного населения Прикамья, недовольного вымогательствами сборщиков ясака и другими притеснениями. После этого волнения в крае продолжались еще несколько месяцев.
Ермак в это время поднимался со своей дружиной все выше и выше по Чусовой. Казаки доплыли до скалы при устье речки Ермаковки (немного ниже поселка Кын), которая позднее получила название «Ермаков камень». Здесь была сделана первая остановка. После этого главные силы Ермака поднялись до устья речки Серебрянки (а небольшой разведывательный отряд, по некоторым сведениям, прошел еще выше — до устья Межевой Утки). Затем дружина стала подниматься вверх по Серебрянке.
Путь по этой маленькой и быстрой речке был очень труден. Большие струги пришлось сразу же бросить, но и струги поменьше проходили с большим трудом. Казаки ставили в воде столбы и, натянув между ними сшитые паруса, запруживали реку. Только так удавалось проводить суда на несколько десятков саженей вперед. Люди надрывались на тяжелой работе, натирали себе кровавые мозоли, мокли в холодной осенней воде. Среди наиболее слабых начался ропот. Но Ермак торопил вперед и вперед: надо было скорее дойти до водораздела и построить там укрепленный городок.
Наконец отряд достиг левого притока Серебрянки речки Кокуя. Здесь на высоком мысу казаки поставили укрепление, которое назвали по имени речки Кокуй-городком. Укрепление состояло из землянок, обнесенных земляным валом и тыном. Теперь Ермак чувствовал себя в сравнительной безопасности: здесь его отряд, в случае необходимости, мог бы выдержать осаду.
Зиму казаки провели в тесных землянках Кокуй-городка. Однообразие зимних скучных буден несколько скрадывали охота, поездки в соседние вогульские поселки, лыжные экспедиции, во время которых казаки добывали продовольствие, старались лучше «проведать» путь в Сибирь.
Весной, когда растаяли глубокие снега и открылись пути по маленьким речкам и речушкам, дружинники перетащили кладь и самые маленькие лодки 25-верстным волоком через тайгу и горы на речку Журавлик, правый приток Баранчи. Здесь казаки сделали лодки и плоты и сплыли на них до реки Тагила.
Эта река была много больше тех горных речек, по которым шел путь Ермака от Чусовой. По ней могли плыть и большие суда. Пройдя несколько верст по Тагилу, дружина сделала остановку у горы Медведь-камень, чтобы построить себе новые струги, взамен брошенных на Серебрянке. Остатки этой стоянки Ермака известны под названием «Ермакова Городища», которое находится на левом берегу Тагила в двенадцати километрах от города Нижнего Тагила и в трех-четырех километрах ниже устья Баранчи. Оно расположено на террасе речной поймы около излучины — очень удобного места для постройки лодок.