Корнелиус Крюйс родился 14 июня 1655 года в норвежском городе Ставангере в семье портного Уле Гундфастесена (? — ноябрь 1668) и его жены Апелуне Кук (1627 — 23 мая 1705). Мальчик родился до того, как его родители поженились, поэтому официальную дату его рождения родители перенесли на 2 года позже. При крещении, проведённом по лютеранскому обряду, мальчик был наречён Нильсом Ульсеном. Будущий российский адмирал изменил своё имя и фамилию только после поступления на голландскую службу. Семья Крюйса была небогатой, но, по понятиям XVII века, и не бедствовала: на отца Нильса Ульсена работал подмастерье, а сам Уле Гундфастесен вырастил шестерых детей — двух девочек и четверых мальчиков, в числе которых был и Нильс. Дом семьи Гундфастесенов располагался в районе Беккенклейва, где в настоящее время (на 1999 год) находится резиденция мэра Ставангера. Когда Нильсу было 7 лет, его семья переехала из Беккенклейва и поселилась на косогоре напротив современной набережной Скаген, чуть ниже и в стороне от существующей башни Валбергторнет. Новый дом семьи Нильса находился всего в 30 — 40 метрах от гавани Ставангера: юный Нильс Ульсен рос в буквальном смысле слова на морском берегу, поэтому неудивительно, что свою взрослую жизнь он связал именно с морем.
В ноябре 1668 года Нильс потерял отца. Вскоре после смерти последнего мать Нильса, Апелуне, отправила 14-летнего подростка Нильса Ульсена в море, определив его, вероятнее всего, на голландский корабль, который и доставил Нильса в Нидерланды. Дальнейшее продвижение Крюйса на голландской службе произошло во многом благодаря его связям с Норвегией и норвежцами — во времена молодости Крюйса между Нидерландами и юго-западной Норвегией существовали тесные связи.
О последовавших 12 годах жизни Корнелиуса Крюйса практически ничего не известно. По собственному признанию Крюйса, в 1672—1673 годах (то есть во время Второй англо-голландской войны) он служил матросом в голландском флоте. Вновь имя будущего адмирала появляется в источниках лишь в 1680 году. Уже тогда он являлся капитаном торгового судна «Африка», бравшего на борт в Лиссабоне соль, сахар и фрукты . Письменные сведения о его морских плавания в этот период отличаются скудостью и крайней неполнотой. Из голландских документов известно лишь, что он работал на девятерых судовладельцев и до поступления на службу в Амстердамское адмиралтейство (1696) побывал в трёх частях света: Европе, Азии, Америке. Подлинно известно, что он посетил Испанию, Португалию, Нидерланды, Данию и некое итальянское государство. Сам же Крюйс, в одном из собственных писем, утверждал, что служил шести монархам и трём республикам.
В 1681 году Крюйс женился на молодой девушке по имени Катарина Фоогт, дочери голландского капитана и купца Клааса Пиетерсона Фоогта и его супруги Жаннетье Янс. Оба новобрачные были протестантами: Крюйс принадлежал к лютеранской церкви, а Катарина — к реформатской. В браке с Катариной у Крюйса родилось пятеро детей, из них двое скончались в детском возрасте. Трое остальных — дочь Юханна (1682) и двое сыновей, Ян (1688) и Рудольф (1690) очень редко видели отца на протяжении многих лет.
Крюйс часто ходил на торговых судах в Португалию и Испанию (Кадис Крюйс посетил ещё во время своей юности). Также он водил корабли в Южную Америку с грузами для голландской колонии Кюрасао, кроме этого занимался доставкой товаров на Кубу. Некоторые исследователи также полагают, что в эти рейсы Крюйс занимался распространённой в ту эпоху работорговлей. Водил Крюйс корабли и в Ост-Индию, в последней, а также в Нидерландах он занимался подъёмом затонувших кораблей.
Во время своих плаваний Крюйсу приходилось и каперствовать. Такого рода занятия в эпоху первоначального накопления капитала были обычным делом капитанов хорошо вооружённых торговых судов. Так однажды, около 1689 года, на обратном пути с Кубы он взял в качестве приза шедшее из Санто-Доминго французское купеческое судно.
Но через два года удача отвернулась от самого Крюйса. В то время шла война между Францией и Нидерландами и корабль Крюйса на пути из Испании в Нидерланды захватили французские каперы. В октябре 1691 года его бывший корабль каперы привели на буксире во французский порт Брест, а самого его бросили в тюрьму.
Попав в столь сложную жизненную ситуацию 36-летний Крюйс не отчаялся. Он обратился к своей семье в Ставангер за доказательствами, что он является норвежцем, то есть датским подданным. Так как Дания не находилась на тот момент в состоянии войны с Францией, то в том случае, если бы Крюйс получил необходимые документы, подтверждающие его датское подданство, захват его корабля и арест его самого следовало бы по французским законам признать неправомерным. Почти полгода Крюйс провёл в тюрьме, прежде чем полицмейстер Ставангера по запросу его матери отослал метрику Крюйса во Францию, а матери выдал её копию. После того как Крюйс заручился необходимыми доказательствами своей принадлежности к датскому подданству, французские власти «выразили сожаление» по поводу захвата капитана корабля из нейтрального государства освободили его из тюрьмы и вернули корабль.
Несмотря на выпавшие на его долю неприятности и на по-прежнему продолжавшуюся войну, Крюйс на протяжении трёх последующих лет продолжал совершать челночные плавания между Кадисом и Амстердамом. Какие грузы доставлял он из Испании в Нидерланды неизвестно. Из Нидерландов же в Испанию он доставлял сыр, который охраняло от корабельных крыс пять кошек. После двадцатипятилетних плаваний по морям и океанам капитан Крюйс стал очень деятельным и искусным специалистом по навигации и кораблевождению, а кроме того, приобрёл хороший военно-морской опыт.
В 1696 году Корнелиус Крюйс завершил свою службу на торговых судах частных судовладельцев и начал служить в амстердамском Адмиралтействе. Хотя Крюйс и был приписан к военному ведомству, тем не менее военного чина он не имел. Поначалу Крюйсу представили лишь временную работу на три месяца, но с октября 1696 года он получил постоянную должность унтер-экипажмейстера. В круг его обязанностей в течение двух лет входили снаряжение и надзор за нидерландскими военными кораблями.
Жизнь на берегу обернулась для Крюйса непредвиденными неприятностями. В сочельник 1696 года расчёт с бондарем за несколько корабельных бочек, починенных им для Крюйса, обернулся для последнего неприятной историей. Бондарь, недовольный низкой оплатой, в бешенстве покинул меблированные комнаты жилища Крюйса, а затем вернулся с большой оравой своих приятелей и крепко ударил унтер-экипажмейстера прямо по лицу, в результате чего Крюйс, моряк немалого роста (около 190 см) был опрокинут на спину, после чего напавшая на него орава ушла, оставив его с больной головой.
В новом, 1697 году, влиятельные чиновники амстердамского Адмиралтейства возложили на Корнелиуса ответственность за недостачи в казне, одновременно обвинив его в погрузке недоброкачественного продовольствия на одно из нидерландских судов. Зимой 1698 года возникла новая проблема — над Крюйсом нависла угроза увольнения и безработицы: война 1688—1697 годов наконец завершилась, а заключение мира влекло за собой неизбежное последствие — сокращение личного состава в военно-морском флоте. Внезапно на жизненном горизонте Крюйса появилась новая надежда: друг Корнелиуса, амстердамский бургомистр Николаас Витсен в ноябре 1697 года намекнул ему, что русский царь Пётр I желает нанять Крюйса для строительства русского военно-морского флота.
Пётр I, в то время находившийся в Нидерландах в составе Великого посольства, первоначально надеялся нанять на русскую военно-морскую службу прославленного голландского вице-адмирала Гилля Шхея, однако тот отклонил предложение царя и со своей стороны вежливо предложил вместо себя кандидатуру Корнелиуса Крюйса. Общаясь с голландскими офицерами и кораблестроителями во время своего обучения на голландских верфях, царь Пётр слышал много лестных отзывов о Корнелиусе Крюйсе, моряке, обошедшем весь мир. По свидетельству очевидцев, Пётр I встречался с Крюйсом и «был очень им доволен». Вероятно, благоприятное впечатление царя от встреч с Крюйсом, а также рекомендации Николааса Витсена, бывшего давним другом Петра I , позволили Крюйсу поступить на русскую военно-морскую службу. Сначала Крюйс колебался, принять или не принять предложение царя Петра: Россию в те времена «считали форпостом варварства перед европейской цивилизацией» , но в конце концов, он согласился и 9 апреля 1698 года подписал контракт о своём поступлении на русскую службу. По условиям контракта Корнелиус Крюйс получил чин вице-адмирала, годовой оклад в размере 9000 гульденов, аванс в размере полугодового жалованья, а также возможность получить прежнюю должность в амстердамском Адмиралтействе, если он не захочет продлить контракт с русскими властями через три — четыре года. В том случае, если неприятель захватит Крюйса в плен, царь обязывался его выкупить. Кроме этого, Крюйсу был предоставлен личный переводчик — Иван Кропоткин, говоривший по-голландски, двое служителей, личный секретарь, пять человек прислуги, среди которых был и лютеранский пастор .
В июне 1698 года на борту одного из четырёх кораблей отправлявшихся в Россию с 600 нанятыми в период Великого посольства голландскими моряками, мастерами и подмастерьями, Корнелиус Крюйс покинул Нидерланды (как оказалось позднее — навсегда). На пути в Россию Крюйс передал своей матери и сестре копию составленного им перед отъездом в Россию завещания, касающегося имущества, унаследованного им в Ставангере от отца. 15 августа 1698 года Крюйс высадился в Архангельске, а ещё через месяц прибыл в Москву .
Пётр I, возвратившийся из Великого посольства в Москву на несколько недель ранее Крюйса, встретил вице-адмирала со всеми почестями. Вскоре после собственного прибытия в Москву Крюйс вместе с царём отправился в Воронеж, куда и прибыл в конце октября 1698 года.
Пётр I, по прибытию в Воронеж, поручил Крюйсу надзор за уже имевшимися в Воронеже кораблями и верфями. Однако, флот, построенный учреждёнными Петром I кумпанствами, оказался в негодном состоянии: Крюйс держался мнения, что полагаться на корабли этого флота не стоит и необходимо приступать к строительству совершенно нового флота с использованием наиболее современных для того времени технологий, ведя строительство силами наиболее квалифицированных корабелов.
Принявшись за вверенное ему дело, Крюйс проявил свойственный ему энтузиазм и крайнюю непримиримость к некачественной работе, медлительности и лени. За весну 1699 года вице-адмирал осуществил сразу несколько дел, которые Пётр I едва ли считал выполнимыми, когда давал их Крюйсу. Адмирал отремонтировал и привёл в «доброе» состояние 58 военных судов, считавшихся до того непригодными для плавания. Одновременно Крюйс возглавил работы по закладке 60 новых кораблей, а также сделал черновые чертежи первого русского 58-пушечного линейного корабля «Гото Предестинация» («Божие Предвидение») и совместно с царём Петром надзирал за его строительством.
После смерти в марте 1699 года первого главы русского военно-морского ведомства — Франца Лефорта, на его место царь назначил Фёдора Алексеевича Головина, человека совершенно не разбирающегося в морском деле и, как полагает Тургрим Титлестад, получившего назначение на этот пост только для того, чтобы не слишком раздражать недругов царя Петра, очень болезненно воспринимавших назначения иноземцев, таких как Патрик Гордон и Франц Лефорт на высокие «командные должности» . Корнелиус Крюйс стал ближайшим советником Головина и, фактически, «истинным руководителем флота».
14 августа 1699 года, вице-адмирал Крюйс во главе русской флотилии из 10 боевых кораблей и 2 галер, отобранных для похода лично Петром I, вышел из Азовского моря на корабле «Благое начало». Флагманом флотилии был 46-пушечный корабль «Крепость» под командованием капитана Памбурга. Вице-адмиралу была поручена важная миссия — доставить в целости и сохранности русского посла Е. И. Украинцева в Стамбул для заключения с турками мирного договора, необходимой гарантии нейтралитета Турции накануне открытия Россией военных действий против Швеции на Балтике..
На рассвете 18 августа 1699 года корабли флотилии Крюйса, на борту одного из которых находился русский царь, бросили якорь в гавани Керчи. Русские корабли в Керчи встретил турецкий флот в составе 4 военных кораблей и 9 галер: оба флота салютовали друг другу из пушек. Турецкая сторона в лице коменданта Керчи Гасан-паши узнав, что русский флот, сопровождающий посольство Украинцева, намерен двигаться Чёрным морем до Стамбула, в течение одиннадцатидневных переговоров добивалась отказа русской стороны от её первоначальных планов, и предложила посольству Украинцева двигаться к Стамбулу сухопутным путём. В итоге переговоров турки пошли на уступки русской делегации, в состав которой входил и Корнелиус Крюйс, и разрешили посольству Украинцева двигаться в Стамбул морем на русском 46-пушечном корабле «Крепость» в сопровождении 1 турецкого корабля. По-видимому, основная заслуга в благоприятном для русской стороны итоге переговоров принадлежала Крюйсу, который будто бы с недипломатичной прямотой заявил после длительных и нерезультативных переговоров:
После благополучной отправки посольства Украинцева Крюйс возвратился в Воронеж. Вплоть до 1702 года Крюйс продолжал трудиться в Воронеже. Он по-прежнему занимался ремонтом и снабжением кораблей Азовского флота. Помимо выполнения своих основных обязанностей, вице-адмирал Крюйс уделял немалое внимание и работам по картографированию Азовского моря и реки Дон, начатым до него русскими и голландскими специалистами. Итогом этой деятельности вице-адмирала стала точная карта Азовского моря и устья реки Дон, изданная в Нидерландах в 1704 году, пользуясь которой можно было проводить российский флот через мелководное устье Дона в Азовское море, и из Азовского моря далее в Чёрное.
В марте 1702 года после четырнадцатидневного пути Крюйс прибыл в Архангельск . Вице-адмиралу лично Петром I было поручено заняться укреплением оборонительной системы города для предотвращения повторных попыток шведов уничтожить единственный русский торговый порт, через который осуществлялась вся внешняя тогровля Московского государства с Западной Европой. Так весной 1702 года русским послом в Нидерландах Андреем Артамоновичем Матвеевым была раздобыта информация о подготовке шведами более крупной, чем в 1701 году, экспедиции против Архангельска.
После прибытия в Архангельск вице-адмирал быстро установил, что с военной точки зрения состояние Архангельска было безнадёжно плохо: крепостные сооружения города были запущены, а два корабля, захваченные в 1701 году у шведов, не были боеспособны и никто не нёс ответственности за их непригодное к военно-морской службе состояние. Несмотря на то, что имелись и оборудование и люди для починки как кораблей, так и укреплений, архангельский воевода Алексей Петрович Прозоровский утверждал, что не получал от царя никаких приказов о начале работ, а поэтому не видел причин содействовать Крюйсу в обоих этих начинаниях.
Так как Крюйс имел под своим командованием 1200 архангельских солдат, он захотел привлечь их к ремонту запущенных городских крепостных сооружений. Однако архангельский воевода вновь воспрепятствовал в этом деле Крюйсу. Пользуясь своими служебными полномочиями, он саботировал деятельность вице-адмирала, приказав солдатам выполнять только те задачи, которые сам считал нужными, а неповиновавшихся своему приказу — пороть. В ответ на протесты Крюйса, воевода отвечал: «В Архангельске правит воевода, а не вице-адмирал» . Исход противостояния между Крюйсом и Прозоровским неизвестен.
Несмотря на противодействие местного воеводы, кое-что для укрепления Архангельска было сделано. Крюйс, как командир архангельской эскадры инспектировал её корабли в Белом море и плавал до знаменитого Соловецкого монастыря. Кроме того, вице-адмирал собирал сведения о ситуации в дельте Северной Двины. Итогом его деятельности стало сосредоточение в руках вице-адмирала важной информации об имевшихся в этой местности ресурсах для борьбы со шведами.
Пётр I, прибывший в конце мая 1702 года из Москвы в Архангельск, сразу после своего приезда занялся строительством архангельских фортификаций и новых военных кораблей. Однако сведения о том, потребовал ли он от Крюйса личного отчёта о происшедших в Архангельске событий, отсутствуют.
В августе 1702 года Пётр I поки