Как следует из послужного списка, 26 марта 1796 г. 24-летний офицер граф Гейден был определен на «бригантин» «Алексей» под командованием капитан-лейтенанта А.К. фон Дирса (кстати, тоже голландца!), «на коем имел плавание от Одессы до Евпатории, Севастополя и Николаева с 27 июня по 30 ноября.
В 1797 году на катер "Христофор" при береге в Николаеве.
В 1798 году марта 19 определён на бригантин "Алексей" и находился при береге в Николаевском порте по 12 мая, потом вышел с флотом на Николаевский рейд, а 29-го июля отправился в море для крейсерства, рейс имел от острова Тендора по Чёрному морю, а 1-го [августа] возвратился ко флоту, и стоял на рейде по 15 ноября.
В 1799 году 26 мая по исправлении порученного мне бригантина, получа из Николаевского порта груз, отправился в Одессу, где взяв таковой же груз, следовал в Севастопольский порт, оттуда прибыл обратно в Николаев с грузом же, по сдаче коего вследствие высочайшего повеления назначен с порученным мне бригантином к отвозу генерал-майора Бороздина в Корфу с гарнизоном, для получения коего следовал в Одессу, а оттуда с оным 4 сентября того же года отправился в назначенный путь, но не доходя до острова Феодосия [Фидониси. - Прим. сост.] за противным ветром возвратились на рейд, где по исправлении некоторых судов починкою отправились паки в тот же путь и прибыли в Константинопольский пролив 27 [сентября], пробыв там до 16 числа октября, отправились в море и прибыли в Корфу 16 ноября...» (РГАВМФ. Ф. 406. Оп. 3. Д. 322. Л. 17 об., 18 об.)
«В 1800 году 10 февраля вышли из гавани острова Корфу и на Коринфском рейде 3 марта, погрузив гарнизон, отправились в Неаполитанское королевство, зайдя по дороге в Бриндизи. Выгрузив гарнизон в Отранто отправились обратно на Корфу.
В 1800 году принял на себя командование фрегата “Иоанн Златоуст” и в составе отряда вице-адмирала Пустошкина, вернувшись на Николаевский рейд, выполняя высочайшее повеление императора Павла I постоянно выходил в море, совершая учебные плавания вдоль берегов от устья реки Днестра до Днепровских лиманов, постоянно возвращаясь в порты» (РГАВМФ. Ф. 245. Оп. 1. Д. 119. Л. 218).
Интересный факт из службы капитан-лейтенанта – с 1795 года за 5 лет своей службы Гейден в отпуске не был.