Работать в первые годы приходилось в невероятных условиях. Постоянно ощущалась нужда в продовольствии, которое его компания должна была доставлять из Охотска, но, как правило, не доставляла. Жили на «подножном корме», на том, что удавалось получить от океана и вырастить в суровых условиях северного климата. К 1799 году А.А. Баранов пришел к убеждению, что Кадьяк — неподходящее место для размещения главной квартиры компании. Он решил перенести ее южнее, в место с более мягким климатом. Свой выбор А.А. Баранов останавил на острове Ситка. К тому времени в связи с неожиданной смертью Г.И. Шелихова А.А. Баранов практически стал неограниченным правителем колонии. Прибыв 15 июля 1799 года на Ситку, он выбрал место на берегу залива и приступил к строительству форта, который в честь Св. Архангела Михаила назвал Михайловским. Прежде всего, была построена большая изба — казарма для служащих и рабочих, затем — дом для самого А.А. Баранова. Первая зима на Ситке была тяжелой. Началась цинга. Запасы продовольствия иссякли, снова пришлось перейти на «подножный корм». Спас неожиданно появившийся у острова косяк сельди. Тем не менее, к весне удалось закончить постройку двухэтажной казармы. Жизнь в форте Михайловском постепенно налаживалась. В дневнике капитана американского судна, посетившего в это время Ситку, есть такая запись. «Недалеко отсюда поселилась большая группа русских и индейцев из племени кодиак. Они охотятся на выдру. Их губернатор ( А.А. Баранов. — Ю. К.) и его супруга присутствовали на ужине. Российский губернатор производит впечатление человека скромного и выдержанного. Его супруга (алеутка. — Ю. К.) опрятна и хорошо одета. Она показалась мне довольно красивой…».
В апреле 1800 года, оставив в Михайловской крепости небольшую группу «промышленных» и алеутов, А.А. Баранов возвратился на Кадьяк. Его авторитет среди служащих РАК к тому времени был уже достаточно высок. Он не только стал коллежским советником, но и неожиданно получил доставленную ему из Петербурга выбитую по приказу Павла I «за усердную службу в американских колониях» специальную золотую медаль.
В 1802 году с Ситки пришли страшные вести: жившее по соседству воинственное племя индейцев напало и уничтожило Михайловскую крепость. Почти все ее защитники были убиты. Однако дела держали А.А. Баранова, полным ходом шла заготовка пушнины. Только в 1803 году в Охотск удалось отправить «мягкой рухляди» на сумму 1,2 миллиона рублей. На побережье Кенайского залива разворачивалась добыча каменного угля, на острове Кадьяк — медной руды. Создавалось медеплавильное производство, главным образом, изготовление медных котлов, пользовавшихся спросом не только у местного населения, но и у испанцев в Калифорнии.
Только в 1804 году А.А. Баранов смог отправиться на Ситку, чтобы отомстить индейцам за разгром в Михайловской крепости. В Ситку под его командой прибыли три небольших судна компании и 300 байдар[9]
с алеутами-охотниками. Какова же была радость А.А. Баранова, когда, войдя в гавань, он обнаружил там фрегат «Нева» подкомандой капитан-лейтенанта Ю.Ф. Лисянского. Узнав о событиях на Ситке, участвовавший в первом кругосветном плавании Ю.Ф. Лисянский, пришел ему на помощь.Флотилия А.А. Баранова подошла к острову в нескольких милях от разрушенного индейцами форта Михайловского. Здесь 29 сентября 1804 года А.А. Баранов поднял русский флаг и заложил новый город. Его он назвал Новоархангельск. Именно основание Новоархангельска и заложило прочный фундамент русской власти на Аляске и Алеутских островах.
В 1806 году для ревизии колонии в Новоархангельск прибыл один из директоров Российско-американской компании, зять Г.И. Шелихова Н.П. Резанов. Колонию он нашел в тяжелом состоянии. Несмотря на все старания А.А. Баранова, люди голодали. Продовольствие из Охотска не поступало. В докладе в С.-Петербург Н.П. Резанов писал: «При всех встретивших меня здесь неудовольствиях от бездны неприятных вещей, мною полученных, нашел я некоторую отраду в том, что убеждения мои каждого к хозяйственной жизни имели некоторое действие. При всей слабости людей и болезни их нашел я здесь вдвое более огородов, засеянных овощами и картофелем, которого достал у бостонцев Александр Андреевич (Баранов. —
Для оказания помощи жителям Новоархангельска Н.П. Резанов приобрел американское судно «Юнона», на котором направился в испанскую колонию в Сан-Франциско. Комендант форта Аргуэльо со своим многочисленным семейством был очарован Н.П. Резановым, и в конечном итоге Н.П. Резанову удалось закупить все, что ему было надо. Во многом в приобретении продовольствия ему помогла дочь коменданта крепости Кончита.