10 (22) ноября 1849 года генерал-губернатор Восточной Сибири Н. Н. Муравьев подготовил представление на
Завойко, а 15 (27) февраля 1850 года последний был назначен исправляющим должность камчатского военного губернатора и командиром Петропавловского порта на Камчатке.
22 февраля (6 марта) последовал указ о соединении в один общий состав под названием 46-го флотского экипажа Охотской мастеровой роты и Петропавловской роты. Охотское штурманское училище также было переведено в Петропавловск, отныне оно стало именоваться «Петропавловским морским училищем» и пользовалось неизменной поддержкой со стороны В. С. Завойко. Из местных средств В. Завойко организовал постройку шхуны «Анадырь», ботов «Алеут» и «Камчадал», 12-весельного катера.
5 (17) августа 1850 года сорокалетний Василий Степанович Завойко вступил в должность первого губернатора Камчатки. Город при нём вырос: если в Петропавловском порту в 1848 году было всего 370 жителей, то в 1854-м — уже 1594, проживавших в 116 деревянных домах. За 1851−1854 годы в Петропавловском порту было возведено несколько десятков зданий различного назначения: склады, торговые лавки, казарма для низших чинов, флигеля для офицерского состава, канцелярия, казначейство, частные дома и другие постройки. Весь город был выстроен исключительно из дерева. Частные дома были крыты травой, а казённые — железом. Были реконструированы портовые сооружения.
23 июня (2 июля) 1853 года Завойко получил чин генерал-майора и утверждён в занимаемой должности губернатора Камчатской области. В должности губернатора он был представлен к новым наградам — ордену Св. Георгия 4-го класса и Св. Анны 2-й степени «с императорской короной», как признание его трудов в освоении столь удаленного края. Именно во время губернаторства Василий Степанович проявил свои лучшие качества как бесстрашный воин, как мудрый стратег и организатор:
На Паратунских горячих ключах выстроен для больных проказою дом и карантин… Местная торговля, имевшая преимущественно меновой характер, производилась обманным образом, причём жертвою являлись камчадалы, не знавшие цены пушным товарам. Завойко поставил торговлю под надзор особого чиновника, на обязанность которого было возложено объявлять камчадалам стоимость их мехов и цену приобретаемых им товаров. Для охранения звериного промысла Завойко приказал прекращать его в начале марта… По его распоряжению из Аяна было привезено 300 коров, которые были розданы жителям Камчатки… Много внимания В. С. Завойко уделял разведению различных сельскохозяйственных культур. Губернатор обязал каждую городскую семью садить не менее 10 пудов картофеля. Ежегодно осенью по его инициативе проводились сельскохозяйственные выставки.