Через год, летом 1715 года, экспедиция Бухгольца на 60 судах отплыла из Тобольска вверх по Иртышу. Достигнув Тары, отряд Бухгольца получил от уездных воевод полторы тысячи лошадей для драгун, которые затем следовали по берегу, обеспечивая безопасность экспедиции.

Отряд насчитывал около 2800 человек: два пехотных и один драгунский полк. Имел артиллерию, стрелковое вооружение, необходимый запас боеприпасов. 

Продвижение экспедиционного отряда Бухгольца проходило без особых осложнений, и к осени 1715 года он достиг Ямышевского озера, известного в то время места добычи соли и находящегося примерно в 450 километрах вверх по Иртышу от устья Оми. 

Высадившись на берег и приступив к строительству крепости, отряд Бухгольца был вынужден вести продолжительные бои с местными кочевыми племенами, которыми руководил джунгарский хан Цэван Раптан. Кочевники не хотели, чтобы русские закрепились в районе Ямышевского соленого озера. Удары, наносимые ими, были достаточно мощными. Снабжение отряда продовольствием и боеприпасами прервалось. 
Кроме того, от ран и болезней стали умирать люди. Учитывая сложившуюся тяжелую обстановку, Бухгольц на военном совете отряда принимает решение с наступлением весны оставить Ямышевскую крепость, спуститься вниз по Иртышу до устья реки Оми и там с остатками отряда (около 700 человек) закрепиться. 

В мае 1716 года отряд Бухгольца высадился в устье Оми, на ее левом берегу. После получения подкрепления и разрешения им строительства крепости на Оми от генерал-губернатора Сибири М. П. Гагарина, Бухгольц приступил к работам. К осени строительство крепости было завершено. 

Немаловажную роль в организации работ сыграл участник экспедиции военнопленный швед, артиллерийский капитан-инженер Каландер, который практически руководил работами по строительству крепости. Примерные границы крепости проходили по современным улицам: Ленина, 10 лет Октября, Стачечной и Почтовой. 

В книге В. И. Кочедамова «Омск. Как рос и строился город» (Омск, 1960. С. 8) так описаны границы первой Омской крепости: «Ее восточная сторона шла от здания библиотеки им. А. С. Пушкина, примерно к пересечению улиц Почтовой и Стачечной. Отсюда она направлялась на юго-восток, а затем под прямым углом зеркально поворочивалась на северо-восток. 
(Южный бастион крепости находился в середине квартала между улицами Рабфаковской и им. Карла Маркса). Западная сторона ограды отклонялась на восток, подходила к территории современной улицы им. 10 лет Октября у предмостной площади». 

22 декабря 1716 года по приказу генерал-губернатора Сибири Гагарина И. Д. Бухгольц, передав командование крепостью и гарнизоном И. Л. Вильяминову-Зернову, выехал в Тобольск, а затем в Москву для дачи Петру I объяснения причин оставления крепости в районе Ямышевских озер. (Умер И. Д. Бухгольц в чине генерал- майора в городе Селенгинске в 1741 году, где в течение шестнадцати лет был комендантом крепости). 

В память основателя города к 250-летнему юбилею Омска, в 1966 году, улице Будочной Куйбышевского района было присвоено имя И. Д. Бухгольца. В 1987 году присвоено имя Бухгольца площади у речного вокзала, там где произошла высадка отряда Бухгольца в 1716 году. 
В настоящее время на здании речного вокзала укреплена мраморная мемориальная доска, напоминающая об этом событии. 

В 1991 году на площади у речного вокзала по проекту скульптора С. А. Голованцева был установлен памятный знак — беломраморная колонна, увенчанная литым двуглавым орлом — гербом Российской державы. В 30-е годы XVIII века юго-западнее и северо-западнее Омской крепости стали появляться первые «обывательские дома», положившие начало гражданским поселениям. Юго-западное поселение было названо Луговской слободой (впоследствии переименованной в Ильинский форштадт), а северо-западное, за рекой Омь, получило название Омской слободы. 

С ростом значения Омской крепости росли и гражданские поселения, укрупнялись старые и появлялись новые форштадты. К началу XIX столетия уже существовали Ильинский, Казачий, Бутырский, Кадышевский, Мокринский, Подгорный, Слободской, Выползки и другие поселения. 

Основными жителями форштадтов являлись отставные солдаты, офицеры, переселенцы и пришлые поселенцы. Левый и правый берега Оми связывали лодочные переправы. 
Весной и осенью связь между частями города прекращалась, это было очень неудобно. Во второй половине 40-х годов XVIII века через Омь, примерно там где сейчас находится Юбилейный мост, был построен наплывной мост. 

Второй после Бухгольца по значимости личностью в истории становления и развития Омской крепости по праву следует считать командира Сибирского корпуса-генерала Ивана Ивановича Шпрингера. И. И. Шпрингер прибыл в Омскую крепость в 1765 году. Это был образованный и высококультурный человек. 
Приняв командование корпусом в 1764 году, он лично осмотрел всю линию укреплений южной границы и пришел к выводу, что в Омской крепости «должно находиться главному теми местами командиру». (Палашенков А. Ф. Памятники и памятные места Омска и Омской области. Омск, 1967. С. 19.) До этого командование Сибирским корпусом находилось в Тобольске. Омская крепость становится официальным центром юго-западной линии оборонительных укреплений Западной Сибири. 

Видя ветхость крепостных сооружений и слабость тыла Омской крепости, сложность из-за водного рубежа снабжения ее гарнизона, особенно в условиях боевой обстановки, и большие неудобства в оперативной связи в период весенне-осенней распутицы с Тарой, Тобольском, Шпрингер. сразу же начал подбирать кадры для проектирования новых крепостей по Колывано-Вознесенской, а также по Иртышской и Горьковской линиям. После настойчивых просьб и разъяснений генерал Шпрингер добивается разрешения на строительство новой крепости на правом берегу Оми. Весной 1768 года было начато строительство новой крепости, которое было завершено в 1771 году. В том же году Иван Иванович Шпрингер умирает. Похоронен он в Омске. 

Примерные границы новой крепости проходили по современным улицам Красина, П. Некрасова, Победы и Таубе. 

Одновременно со строительством новой крепости в конце шестидесятых годов XVIII столетия через реку Омь был построен первый мост на деревянных сваях. В последующие годы строительство новых деревянных мостов на сваях проводилось в 1795, 1826, 1870 годах, последний из них был заменен железным мостом в 1903 году. 

Возведенная генералом Шпрингером новая крепость выгодно отличалась от старой. Она занимала около 30 гектаров, располагала четырьмя бастионами и тремя полубастионами. К 1805 году Омская крепость считалась одной из лучших в системе Западно-Сибирских оборонительных линий. К этому времени ее гарнизон состоял из 3463 солдат и нижних чинов при 92 офицерах. 
В истории Омска есть и трагические события, которые оставили свои следы в развитии города на долгие годы.