В 1696 г. Корнелиуса пригласили на службу в амстердамское Адмиралтейство, где он получил должность унтер-экипажмейстера. В круг его обязанностей входили снаряжение и надзор за голландскими военными кораблями. Должность была временной, на период войны между Францией и Нидерландами, к тому же хлопотной. В период ее исполнения Корнелиус был и бит подрядчиками, и обвинен чиновниками в мошенничестве. Но главное то, что война (1688–1697 гг.) заканчивалась, и 42-летний моряк мог оказаться безработным.
Тут-то и свела судьба Корнелиуса с русским царем, который постигал тогда в Голландии искусство строительства морских судов. Петр предложил Крюйсу службу в России. После некоторых колебаний Корнелиус принял предложение, подписав соответствующий контракт 9 апреля 1698 г. Колебания были неслучайными. В Европе в то время существовало мнение, что Россия является «форпостом варварства перед европейской цивилизацией».
Однако условия службы были заманчивыми. В контракте отмечалось, что Крюйс, не имевший в Голландии никакого военного или военно-морского чина, принимается на русскую службу в чине вице-адмирала с ежегодным окладом 4000 рублей. Кроме того, ему положено 36 четвертей муки да 72 рубля на содержание денщиков, личный секретарь и личный переводчик с голландского. Здесь же отмечалось, что Крюйсу гарантируется получение прежней должности в амстердамском Адмиралтействе, если он не захочет продлить контракт с русскими властями через три года, а в случае захвата его в неприятельский плен русские власти обязуются его выкупить.
В сентябре Крюйс прибыл в Москву, где царь встретил его со всеми почестями. Началась его русская служба, которая продлилась до самой кончины. Для начала Крюйс составил первые правила морской службы, заимствуя их из уставов голландского и датского флотов. Затем Корнелий Иванович отправился на юг России, где принял участие в строительстве Адмиралтейства в Воронеже, Таганрогского порта и укреплений в Азове. При этом он составил атлас и описание реки Дон, а также карту Азовского моря.
Затем, в 1702 г., Крюйс отправился в Архангельск. Здесь он готовил город к обороне, ходил с Архангельской эскадрой в Белое море до Соловецкого монастыря и селения Нюхчи в Онежском заливе, а осенью отправился на иностранном купеческом судне в Голландию. Здесь он заведовал наймом иностранцев для русского флота и распределением по кораблям, портам и школам посланных с ним русских юношей для обучения их морскому делу и кораблестроительному мастерству. В эту поездку Крюйс принял к себе секретарем 19-летнего Генриха Остермана, ставшего впоследствии российским вице-канцлером, а также завербовал будущего полярного путешественника и российского адмирала Витуса Беринга. В Голландии Корнелий Иванович напечатал свою карту Азовского моря и устья реки Дон, пользуясь которой российские капитаны успешно проводили свои суда через мелководье Дона в Азовское море.