Годом основания этого сибирского города считается 1856. Именно в это время было начато строительство Усть-Зейского военного поста. К 1856 Российская Империя крайне нуждалась в окончательном закреплении левого берега Амура в собственность государства. Для этого было нужно срочно предпринять меры по закреплению левобережных территорий. Так началось заселение этих мест русскими.
В 1856 неподалеку от устья Зеи на левый берег Амура прибыл военный отряд. Его численность составляла 5 сотен солдат. Они занялись расчисткой территории, готовя ее к строительству острога – укрепленного места для будущих переселенцев. Были выкорчеваны обширные участки не только под размещение поселения, но и под огороды и пашни. В скором времени прибыла первая группа поселенцев. В ней было всего 60 человек. Большей частью это были забайкальские казаки. Руководил ими М. Г. Травин.
Задачей первой группы поселенцев была необходимость продержаться в остроге зиму, чтобы новые поселенцы, прибытие которых намечалось на следующую весну, смогли сразу обосноваться и начать ведение хозяйственных работ. Казаки стерегли склады с продовольствием, охраняли почтовую связь, а также строили избы для тех, кто должен был прибыть весной.