Н. А. Добровольский служит там почти шесть лет, прибавляет к своим наградам орден Святой Анны 2-й степени и серебряную медаль в память царствования императора Александра III, а также получает чин статского советника. После этого он круто меняет направленность своей деятельности — неожиданно оставляет Министерство юстиции и переходит в систему Министерства внутренних дел. Высочайшим приказом от 8 февраля 1897 года его назначают гродненским вице- губернатором. Три года он занимает эту должность, часто замешает отсутствующего губернатора, а в последний год вообще полностью принимает на себя управление губернией. В апреле 1899 года без освобождения от основных обязанностей он назначается на три года почетным мировым судьей Гродненского округа и впоследствии занимает это престижное место еще дважды.
В феврале 1900 года пришло высочайшее повеление — Добровольский становился гродненским губернатором. На этом посту он дослужился до действительного статского советника, получил почетный чин камергера двора его величества и удостоился двух экзотических иностранных орденов — Персидского льва и Солнца 1-й степени и черногорского князя Даниила Первого 1-й степени. Через восемь месяцев он уволился и тут же был утвержден обер-прокурором первого департамента Правительствующего сената.
В системе Министерства внутренних дел Добровольский так и оставался до Февральской революции. С октября 1906 года он уже сенатор, в декабре получает придворный чин егер-мейстера. Современники уважительно называют его «знатоком административного права». Он чуть было не становится министром внутренних дел, но не только обширные профессиональные знания стали причиной его выдвижения на этот пост — дело имело еще один нюанс. Добровольский всегда был близок к высочайшему двору, но теперь он особенно тесно общался с кругом лиц, сплотившихся вокруг теневого лидера — Григория Распутина. Но министром Добровольский все же не стал — императора его кандидатура почему-то не вполне устраивала.
Впрочем, это не значит, что он был обделен высочайшим вниманием — 1 января 1914 года ему вручают еще один орден, на этот раз Белого Орла. В сентябре 1916 года он оставляет пост обер-прокурора и сосредотачивается на своих сенаторских делах. Ко всему прочему его избирают заместителем председателя Георгиевского комитета.
Но к концу 1916 года Г. Распутин опять пытается вмешаться в государственные дела — ему не нравится, что неуступчивый министр юстиции А. А. Макаров никак не желает прекращать дела бывшего военного министра Сухомлинова и известного мошенника Манасевича-Мануйлова. Тогда Распутин затевает свою интригу — начинает особенно настойчиво добиваться назначения Добровольского на пост генерал-прокурора. По свидетельству С. П. Белецкого, видевшего Распутина за два дня до его гибели, у него было «жизнерадостное настроение и полное удовлетворение по случаю полученного им обещания о назначении на пост министра юстиции Н. А. Добровольского, при посредстве которого он рассчитывал добиться окончательного погашения дела Сухомлинова».
