После отстранения Безкровного обязанности наказного атамана были возложены на генерал-майора Н.С. Завадовского, официально утвержденного в этой должности 25 сентября 1837 г. Родился Завадовский в 1789 г., на службу был зачислен в 1800-м, и жизнь его, как отмечал Е.Д. Фелицын, протекала в основном в походах и сражениях с неприятелем: он участвовал в Отечественной войне 1812 г., русско-турецкой, Кавказской…

Управление Черноморией Завадовский принял в тяжелые для нее годы: вслед за эпидемией холеры был повсеместный на Северном Кавказе неурожай. Проезжая через округа Екатеринодарский, Бейсугский и Ейский, наказной атаман «почти везде видел бедность и нищету войсковых жителей, худые кровли, неогороженные дворы, не имеющие в себе ни хлеба, ни сена…»

В 1832 г. во главе с атаманом был создан комитет по выработке положения о Черноморском казачьем войске. Таковое положение было утверждено 1 июля 1842 г. Согласно ему наказной атаман по военной части получал права начальника дивизии, а по гражданской — губернатора, куренные селения преобразовывались в станицы, регламентировались и другие вопросы управления войском.

В 1848—1849 гг. в Черноморию были переселены 20 тысяч семейств из Малороссии, пополнившие поредевшее население старых станиц. В 1849 г. Екатеринодар получил свой герб. Жизнь в городе и станицах шла своим чередом, но атаман мало принимал в ней участия, потому как преимущественно находился вне войска, то в Ставрополе, где было местопребывание командующего войсками на Кавказской линии и в Черномории (этот пост он также занимал), то за Кубанью, в военных экспедициях. Там и постигла его смерть 9 ноября 1853 г.

Завадовский тяжело заболел, тем не менее несмотря на решительный протест доктора приказал продолжать путь, но следующего привала уже не дождался.

Командующий отдельным кавказским корпусом князь Воронцов в своем приказе от 19 ноября 1853 г. высоко оценил боевые заслуги атамана. Заканчивался приказ словами: «Почтенному генералу от кавалерии Завадовскому честь и слава…»