В середине XVII века началась русская колонизация земель, лежащих за озером Байкал. Множество казацких отрядов было разослано в самые отдаленные уголки Российской империи, чтобы разведать земли, обложить местных жителей ясаком и обнаружить месторождения серебра и золота.
Одним из таких отрядов командовал баргузинский казак Гаврила Ловцов. Он пробирался вниз по течению Уды, но река замерзла и он вынужден был остановиться, чтобы перезимовать. В том месте, где сливаются реки Уда и Селенга, было построено временное зимовье, которое назвали Заудинским камушком. О его постройке задумывались и раньше – ведь одного Селенгинского острога не хватало для того, чтобы эффективно собирать ясак.
В период 1677-1680 года, на месте зимовья построили укрепленный пятибашенный острог, в гарнизоне которого находилось всего два десятка казаков. Основным их занятием был сбор ясака. В это время началось активное сопротивление русской колонизации местным населением, поэтому Удинский острог приобретает не только торговое и административное, но и военное значение. В 1682 году крепость была осаждена монгольскими феодалами под руководством тайши Гыгана, но гарнизон спас отряд бурятского племени хори.