Определённый в Олонец губернатором, Державин вместе с женою отправился повидать старуху мать, которой было уже за шестьдесят лет. Но им не суждено было застать её в живых: Фёкла Андреевна скончалась за три дня до их приезда. Державин и Катерина Яковлевна и несколько лет спустя без слёз не могли вспоминать о том, как откладывали-откладывали эту поездку, да и прибыли слишком поздно…
Олонецкая губерния вместе с Архангельскою составили новое наместничество, во главе которого Екатериною II был назначен генерал-поручик Тимофей Иванович Тутолмин. Прекрасный собою, большого росту мужчина, он получил образование в царствование Елизаветы Петровны в шляхетском корпусе и, участвуя в Семилетней и первой турецкой войнах, пользовался особливым расположением знаменитого Румянцева. Он командовал Сумским гусарским полком, который до того хорошо был выучен маневрировать, что после замирения с Фридрихом II Румянцев хвастался всегда перед приезжавшими к нему пруссаками, посылая их смотреть ученья этого полка. Однако Тутолмин, умевший довесть своих гусар до желаемого им совершенства, по части сражений был не великий охотник. Полк его дрался отлично; турки узнавали сумцев по жёлтым мантиям и бежали вспять. Тутолмин всегда бывал с полком, но сзади, а не впереди гусар своих. Румянцев ожидал, ожидал, не попривыкнет ли он к бою, не ободрится ли, и наконец сказал:
– Ты знаешь небось, Тимофей Иванович, сколь много я тебя уважаю и сколь мне будет прискорбно расстаться с тобою. Но говорю тебе дружески: не годен ты для войны. Вот тебе всеподданнейшее письмо моё её величеству. Всемилостивейшая государыня соизволит употребить тебя на поприще службы гражданской. Уверяю тебя, мой друг, в непродолжительное время ты достигнешь высоких чинов и приобретёшь полное доверие монархини…
Проницательный Румянцев в плохом воине разглядел дельного администратора. Через год Тутолмин был тверским вице-губернатором, через два – тверским губернатором, через три – губернатором екатеринославским, а затем – архангельским и олонецким наместником, кавалером ордена Александра Невского и Владимира 2-й степени. Сверх возложенной должности управлять губерниями Тутолмин имел от государыни наказ устроить в Олонце чугуноплавильный завод для литья на флот пушек. Славный мастер Гаскони, англичанин, был переманен и украдкою вывезен из Лондона. Скоро и неожиданно завод был хорошо устроен; литье пушек из чугуна превосходило отливку из меди на питербурхском заводе, что очень пригодилось в начавшейся вскорости войне со Швецией.
Сам Державин отзывается о Тутолмине лишь как о сумасброде, но здесь поэту верить трудно. Другое дело, что, считая себя первым администратором России, Тутолмин был страстный охотник до реформ, проектов и нововведений. Всё, что императрице случалось высказать в качестве желательной реформы в будущем, он немедленно приводил в исполнение у себя в виде пробы, отчасти, чтоб угодить императрице, а отчасти, чтоб прослыть просвещённым человеком.
К началу царствования Екатерины II в России насчитывалось всего шестнадцать губерний, учреждённых Петром Великим. После подавления пугачёвского восстания было образовано ещё двадцать четыре. В каждой из сорока назначался правитель или губернатор, а над ним ставился наместник царицы или генерал-губернатор, которому подчинялось две-три губернии. Таким путём Екатерина II стремилась укрепить администрацию на местах. Однако пределы власти наместника и губернатора не были в точности означены, что уже могло содержать в себе источник недоразумений и раздоров.
Вновь организованная Олонецкая губерния существовала пока что лишь на бумаге. Непроходимые леса и болота, тысячи озёр покрывали этот малолюдный, никогда не знавший помещичьего произвола край. Олонецкие крестьяне платили подати государству, и лишь часть их работала на Петровском и Коячезерском железных заводах. По числу населения (206 тысяч) новая губерния уступала прочим, зато обширностью превосходила многие.
Новая должность представлялась Державину очень важной. Он полагал искоренить злоупотребления чиновников, строго блюсти законы, держать в узде хищную ораву присяжных и насаждать просвещение. Зная, что в губернском правлении нет ещё ни столов, ни стульев, новый губернатор понакупил мебели и вместе со своею обширною библиотекой отправил всё это по Неве, Ладожским каналам и Свири. Чтобы набрать нужную сумму, Державину пришлось заложить некоторые женины и свои драгоценности и, между прочим, табакерку, пожалованную ему за «Фелицу».
В начале октября 1784-го года он прибыл в Петрозаводск вместе с семьёй, а также канцелярскими служителями, в числе которых был Андриан Моисеевич Грибовский, весьма образованный выходец из Малороссии. Державин занял один из шести имевшихся в городе деревянных, обложенных кирпичом домов на Английской улице, названной так потому, что на ней жили выписанные для завода мастера-англичане. 9 декабря 1784-го года губерния торжественно была открыта; празднества продолжались целую неделю.