В 1898 году окончил Морской кадетский корпус. Во время русско-японской войны служил минным офицером на крейсере «Аврора» в составе 2-й Тихоокеанской эскадры. Был ранен в Цусимском сражении и за отличие был награжден орденом Св. Анны III степени с мечами и бантом.
В 1912 году произведён в капитаны 2 ранга и награжден мекленбург-шверинским орденом Грифа 4-й степени. Командовал эсминцами «Сильный» (1912—1914), «Страшный» (1914—1916), «Донской казак», 5-м и 12-м дивизионами миноносцев. Участвовал во многих боевых операциях и боях, занимался постановкой минных заграждений под Виндавой, на которых погибло несколько немецких миноносцев и крейсеров. 6 декабря 1916 года произведен в чин капитана 1-го ранга. В 1917 году командовал Минной дивизией Балтийского флота. 28 июля 1917 года произведён в контр-адмиралы. Уволен в отставку 3 апреля 1918 года.
Прибыл в Казань в августе 1918-го, вступил в армию Комуча и возглавил Волжскую флотилию белых. После оставления бассейна Волги действовал на реках Каме и Белой. Назначен А. В. Колчаком формировать в Красноярске Бригаду (декабрь 1918-го), а затем — Дивизию морских стрелков, во главе которых прошёл весь путь отступления Белых армий в Сибири. Отходил вместе с войсками генерал-лейтенанта (1919) В. О. Каппеля. Заболев тифом, через Байкал был перенесён в феврале 1920 года на руках в бессознательном состоянии. Лечился в Харбине.
17 июня 1921 года прибыл во Владивосток по просьбе правительства Приморской области и возглавил Сибирскую флотилию — последнее действующее объединение кораблей Русского флота под Андреевским флагом. Старку удалось восстановить и привести в порядок значительное число кораблей, подготовить их к эвакуации остатков белых сил и беженцев.
23 октября 1922 года увёл из Владивостока остатки Сибирской флотилии, имея на борту 10 000 беженцев. Всего ушло 30 кораблей: канонерская лодка «Манчжур», вспомогательные транспорты, пароходы, военные буксиры, посыльные суда, катера. Флотилия Старка пришла в корейский порт Гэндзан, в то время находившийся под японской оккупацией, а затем в Шанхай, где высадила гражданских лиц, а затем на Филиппины. По прибытии в Манилу, Г. К. Старк продал остатки флотилии и пароходы Добровольного флота. Все деньги, вырученные от продажи, и тот небольшой запас золота, который вывезли при эвакуации, адмирал разделил поровну среди нижних чинов и офицеров бывшей Сибирской военной флотилии.
Финансовый и военно-политический отчет по Флотилии направил великому князю Николаю Николаевичу. Переехал в Париж, где многие годы работал шофёром такси. В политической деятельности участия не принимал. Во время оккупации Парижа немцами (1940—1944) отказался сотрудничать с германскими властями.
Председатель Всезарубежного объединения русских морских офицеров (1946—1949). Умер под Парижем. Похоронен на кладбище Сент-Женевьев-де-Буа.
Жена — Елизавета Владимировна Развозова, вдова лейтенанта Мессера (29.06.1881, Виндава — 29.05(11.06)1924, Петроград)