Для устранения отмеченных недостатков Я. Е. Сиверс предлагал оставить «при Олонце» 21 471 душу государственных крестьян, а при Вянгинской пристани в устье реки Вытегры учредить город и воеводскую канцелярию. Эта пристань должна была стать административным центром южной части уезда по следующей причине: «Не столько полза обывателей сей части Олонецкого уезду, но более народная и казенная в течении чрез сие место некоторой части внутренних продуктов побуждают меня к представлению в сие место городского правления». Третье, по выражению Я. Е. Сиверса, «отделение» Олонецкого уезда должны были составить Лопские погосты. Паданский погост, по мнению Я. Е. Сиверса, представлялся «за способнейший, чтоб в оном учредить комиссарское правление по штату при городе с полномочием принять в платеж государственные поборы, и суд, и расправу над оными Лопскими погостами».
Действительность (прежде всего воссоздание Петрозаводской слободы, в которой возобновлялось «пушечное литье») внесла коррективы в планы генерал-губернатора, и вскоре он выступил с новыми предложениями. Находя, что в составе Новгородского наместничества недостаточно городов, Я. Е. Сиверс предложил преобразовать слободу Петровского завода в город, поскольку считал, что она может скоро разбогатеть «благодаря своему мрамору, железу и промышленному духу жителей Олонецкой провинции».
21 марта 1777 г. появился указ Екатерины II, предписывавший переименовать Петрозаводскую слободу в город, «которому и быть на основании прочих Олонецкого наместничества городов». Далее по указу от 11 декабря 1781 г. город Петрозаводск вместе со всей Олонецкой провинцией, был присоединен к Петербургской губернии. В то же время областные учреждения в Олонецкой провинции остались на прежнем месте. Однако Олонец уступал свое первенство Петрозаводску, положение которого было сочтено более подходящим для административных целей. И указом от 12 мая1782 г. было повелено перенести сюда из Олонца провинциальное правление. В том же году, с упразднением города Паданска, был учрежден город Повенец, к которому приписан Паданский округ. Одновременно был образован Вытегорский уезд, который состоял из территории бывшего Вытегорского погоста с присоединением к нему Оштинского погоста и нескольких волостей из соседнего Белозерского уезда.
Создание в 1784 г. Олонецкого наместничества на правах губернии стало принципиально новым этапом в административной деятельности на территории Карелии. Наместничество состояло из 8 уездов: Петрозаводского, Олонецкого, Каргопольского, Лодейнопольского, Вытегорского, Повенецкого, Пудожского и Кемского. В конце 1796 г. оно было упразднено, а в 1801 г. — восстановлено как губерния в прежних границах, кроме Кемского уезда, оставшегося в составе Архангельской губернии. Олонецкая губерния стала одной из самых обширных в государстве. Однако по количеству жителей она занимала одно из самых последних мест. Строго говоря, при ее создании был нарушен главный принцип создания губерний: согласно законодательству, предполагалось, что численность населения губернии должна составлять 300-400 тыс. человек, а в установленных границах Олонецкой губернии насчитывалось чуть более 200 тыс.
Образованию Олонецкой губернии способствовал целый ряд обстоятельств: возросшее в связи с возобновлением русско-турецких войн значение Олонецких горных заводов, поставлявших артиллерийские орудия и боеприпасы для Черноморского флота, новое обострение отношений со Швецией и стремление укрепить русско-шведскую границу. Третьим существенным фактором явилась относительная отдаленность Карелии от крупных административных центров севера и северо-запада страны — Архангельска, Вологды, Новгорода, Петербурга.
Первым олонецким губернатором стал Г. Р. Державин. В соответствии с законом на губернатора возлагался обширный круг обязанностей. Прежде всего, он был обязан наблюдать за действиями всех остальных должностных лиц в губернии и за исполнением законов. Надо сказать, что эта обязанность всецело вписывалась в систему убеждений Г. Р. Державина, который полагал, что наведение порядка в местном управлении зависит исключительно от добросовестного отношения чиновников к делу и неукоснительного соблюдения законодательства. По этой причине уже через месяц после образования губернии все подведомственные учреждения были поставлены в известность о том, что каждый чиновник или иное лицо, находящееся на государственной службе и виновное в нарушении законов, будет наказано, по мере важности его упущений, лишением места или чина.
Во-вторых, на губернатора возлагалось попечение о нуждах населения: то есть, являясь представителем центрального правительства, губернатор в то же время должен был стать «ходатаем за пользу общую, заступником угнетенных и возбудителем безгласных дел» (таких, в которых в качестве истца выступает само государство). Надо сказать, что многие губернаторы, находясь в губернии в течение относительно короткого времени, не успевали вникнуть во все местные условия, что, конечно же, препятствовало трезвой оценке ситуации. Так, вскоре после прибытия Г. Р. Державин велел передать находящимся в губернии старообрядцам, что отныне им запрещается «сжигать самих себя». Узнав о том, что значительная часть крестьян добавляет в хлеб сосновую кору, он предпринял специальное расследование и установил, что единственной причиной является крайняя скупость крестьян, не желающих покупать хлеб.
Помимо обычных трудностей, присущих управлению любой губернией, Г. Р. Державин столкнулся с необходимостью формирования административного аппарата. Это было чрезвычайно непростой задачей. С хроническим недостатком грамотных чиновников олонецкие губернаторы сталкивались постоянно. И Г. Р. Державин регулярно получал с мест донесения о том, что в суде «должность секретаря никто не исправляет, отчего предвидится в делах остановка». Отчасти вакансии в присутственных местах были заполнены недавними студентами, которых привез с собой из Санкт-Петербурга Г. Р. Державин. Отчасти способ, при помощи которого заполнялись вакансии, виден из доношения председателя судебной палаты. Председатель сетовал на невозможность «с желаемым успехом вести дела», поскольку оформлением бумаг в канцелярской части занимаются «худо умеющие писать дети от 12 до 14 лет». Подобных «малолетов», как их тогда называли, приходилось привлекать для различных вспомогательных работ и в других правительственных учреждениях.
Однако, несмотря на все трудности, первому олонецкому губернатору удалось открыть все присутственные места, положившие начало трем группам учреждений местного уровня: административным, финансовым и судебным. Высшим административным органом в губернии являлось губернское правление, в состав которого наряду с председателем — губернатором — входили два советника, игравшие совещательную роль. Губернское правление выполняло двоякую функцию: во-первых, обнародовало указы верховной власти, а во-вторых, принимало меры полицейского характера. В уездах губернскому правлению соответствовал нижний земский суд.
Финансовое управление было отделено от общеадминистративного и велось казенной палатой, состоящей под председательством вице-губернатора из четырех членов и губернского казначея. Основой деятельности палаты было ведение налогового учета. Наибольшая часть дохода, поступавшего в распоряжение палаты, состояла из налогов, выплачиваемых крестьянами. Например, в 1792 г. крестьяне выплатили 349 120 руб., при общем казенном доходе по губернии в 466 103 руб. На втором месте по удельному весу в сумме налогов стоял питейный сбор. Что касается платы с купеческих капиталов и доходов от казенной и частной промышленности, то они составляли незначительную часть местного бюджета. На расходы в губернии оставалось менее одной четверти собранных средств. Остальные деньги отправлялись на содержание армии и Адмиралтейства, а также в Государственное казначейство, расположенное в Санкт-Петербурге.
Высшим судебным учреждением в губернии являлись две палаты — гражданского и уголовного суда, состоящие каждая из председателя и четырех членов, назначаемых правительством. В палаты поступали дела из низших судебных инстанций: в апелляционном порядке по жалобам сторон и в ревизионном — для утверждения приговоров. Такое восхождение по инстанциям до палаты в ревизионном порядке было обязательно для тех уголовных дел, в которых наказанием могло стать лишение подсудимого жизни или чести.
