«Через посредство графа Головкина, бывшего послом нашим в Голландии, и графа Маркова, граф Гейден был представлен императрице Екатерине II, обласкан ею и принят в русскую службу, 10 ноября 1795 года, с чином капитан-лейтенанта, и с назначением тогда в Черноморский гребной флот, содержащейся в Одессе» (Воспоминания…, С. 522).
Императрица высоко оценила опыт, знания, происхождение иностранного офицера. Политический эмигрант, опытный моряк оказался в нужное время в нужном месте, так как правительство Екатерины II предпринимало чрезвычайные меры по усилению Черноморского флота. Об этих «приуготовлениях» мы узнаем из секретного письма императрицы Екатерины II маркизу де Рибасу от 16 января 1794 г. «Получая известия о чинимых от стороны Порты Оттоманской сильных приуготовлениях восстать против нас войною и о намерении турков разорвать торжественные обязательства свои в сохранении мира; осторожность и польза России требует, чтобы все морские и сухопутные силы её немедленно приведены были в исправность и готовность не токмо отразить силы турецкие, но и обратить оружие наше нападательно и ввести как сухопутные войска наши, так и гребной флот Черноморский в вашем начальстве состоящий в пределы областей турецких» (РГАВМФ. Ф. 245. Оп. 1. Д. 123. Л. 20).
В высочайшем рескрипте были обозначены необходимые мероприятия, одним из важных направлений являлось усиление гребного флота: строительство кораблей и приём на службу вольных матросов и иностранных специалистов. Именно здесь началась успешная служба капитан-лейтенанта Л.П. Гейдена.