Не видя перспектив роста в английском флоте мирного времени, где шотландцев не жаловали, Грейг решил перейти на иностранную службу. В то время Екатерина II, вступив на престол, готовилась осуществлять грандиозные политические планы. Ей был необходим боеспособный флот. В строю недоставало опытных моряков, их приглашали из-за границы. По поручению Императрицы посол в Англии С. Р. Воронцов подбирал офицеров-мореходов. Грейг принял приглашение и обратился с ходатайством в британское Адмиралтейство. Уже 7 мая 1764 года он получил разрешение поступить на русскую службу. Вскоре Грейг выехал в Россию. 18 июня появился указ о приеме на службу группы офицеров (трое из них были шотландцы). Грейга сразу, через два чина, произвели в капитаны 1-го ранга, но в кампанию 1764 года ему, как и другим иностранцам, для «скорейшего познания обрядов нашей службы», предстояло служить волонтером на эскадре адмирала А. И. Полянского. На подлиннике указа об этом Екатерина II собственноручно приписала: «Старшинством считать капитана Грейга с 20 марта… 1764 года».
В 1764 году дублером командира единственного российского 100-пушечного корабля «Святой Дмитрий Ростовский» в эскадре адмирала А. И. Полянского, следующим летом командиром фрегата «Святой Сергий» в эскадре адмирала С. И. Мордвинова Грейг ходил по Балтике. Именно с этого времени он начал вносить свой вклад в совершенствование Российского флота.
Моряк представил Адмиралтейств-коллегии новый способ вооружения военных судов, испытанный им на своем фрегате. Точнее сказать, Грейг не столько придумал нечто новое, сколько предложил ввести на корабли Российского флота то, что уже использовали в практике британского флота.
29 июля 1765 года Грейг докладывал коллегии о сделанных им на фрегате нововведениях. Шканцы удлинили от бизань-мачты к грот-мачте для лучшего расположения людей во время работы на судне. Снасти распределяли так, чтобы «одна от другой лежали свободно, дабы избежать замешательства, ежели случится, что все матросы сбегутся на один палуб, и снасти ходячие не лежали бы одна чрез другую и во время баталии для лучшего употребления мелкаго ружья».
Шпиль сделали двойной, чтобы вращать его можно было с верхней и нижней палуб одновременно; это позволяло поднимать якорь в непогоду, увеличить скорость подъема за счет большего числа моряков, работающих на шпиле. Кроме того, матросы на верхней палубе были готовы работать с парусами, как только якорь оторвется от грунта. Грейг сделал на фрегате мачты короче и реи тоньше, что облегчало работы при постановке парусов, повышало остойчивость судна, и увеличил количество парусов на мачтах.
Для штормовых условий он же предложил уменьшенные паруса: грот, фок и марсели, а для плавания в тихую погоду — увеличенные стаксели, брамсели, грот и фор-марсели. Моряк отмечал, что лично он придумал делать верх фор-марселя, грот-марселя и брамселей с выемкой сверху дугой, чтобы паруса не полоскали; снасти он рекомендовал упростить, уменьшив число блоков.
22 августа 1765 года Адмиралтейств-коллегия приняла решение достраивать один из кораблей с изменениями, предложенными Грейгом. 3 апреля 1766 года Грейга определили командиром на строящийся 66-пушечный корабль, который при спуске назвали «Трех Иерархов». С разрешения Екатерины II моряк оснастил его по-новому, превратив в образец для кораблей и фрегатов. Он сократил высоту мачт, увеличил парусность за счет кливеров, стакселей, ввел четвертый ряд парусов на фок- и грот-мачтах, что повысило остойчивость и скорость, кроме того, увеличена была площадь стакселей и брамселей, изменен покрой парусов для сохранения лучшей формы на ходу, а также расширены были марсы, тоньше и легче сделаны реи, упрощена проводка бегучего такелажа, снято много лишних блоков. К списку усовершенствований моряк добавил следующий комментарий:
«Искусство состоит в опыте или примечании морской практики, отчего всякий корабль может лучше иметь ход, понеже в Англии всякий капитан власть имеет на своем корабле к лучшему ходу во всем перемену делать, и для того де, с самого лучшего в ходу в английском флоте 66-пушечного корабля, по великости онаго, взял он ту препорцию, чему приложил роспись как у нас по штату положено и какую он сделал отмену и прибавку».
В России такая вольность была новинкой, да и англичанам, как оказалось, не все было дозволено делать. Вице-адмирал Г. А. Спиридов, признав полезными нововведения Грейга, отметил, что в Англии, если скорость судна в результате усовершенствования не возрастет, убыток от переделок возлагается на капитана.
26 августа 1767 года Адмиралтейств-коллегия слушала предложение Грейга для предотвращения гниения обмазывать корпуса военных и купеческих судов не чистой смолой, а смешанной с серой (по образцу английского флота) и приказала выполнить сие при килевании его корабля.
В январе 1768 года «Трех Иерархов» подвергли испытаниям. Г. А. Спиридов отметил, что корабль движется несколько быстрее других и Грейг заслуживает похвал, но дальнейшие решения оставил на усмотрение Адмиралтейств-коллегии. Екатерина II, заинтересованная в совершенствовании флота, 27 ноября запросила, какая оснастка кораблей лучше: прежняя либо предложенная Грейгом. Коллегия в журнале за 22 декабря отметила:
«…Баршу[1] порученный корабль был вооружен по здешнему положению, а Грейгов по его разсуждению и испробованы на море все время кампании 1767 года под командою вице-адмирала Спиридова, который представлял, что… пред прочими бывшими в эскадре кораблями имея одинакие паруса, ходили несколько скорее; между же собою в ходу, начиная от брамселей, когда можно было нести, под равными парусами были почти одинаковы… А когда ветр и время дозволяли на оном корабле „Трех Иерархов“ кроме настоящих, какие и на других, излишние у него паруса еще поставить, тогда ходил скорее корабля „Три Святителя“; егда же случались ветры легкие брамсельные что на оном корабле „Трех Иерархов“ можно было нести не точию три брамсели, но и бовен-брамсели, стаксели и все верхние и нижние паруса от бейдевинда и ниже доколе во все паруса ветр дул, то по излишеству парусов не точию против прочих, но и перед кораблем „Три Святителя“ ход имел по силе ветра многим скорее… Почему коллегия определила: позволяя перемену в парусах, в блоках и в оснастке, исходя из Грейгова представления способным несколько прибавочных парусов, ибо не можно на сие сделать всеобщего положения, как то зависит от состояния корабля по его образу построения, а по оному и отдать то должно искусству капитанов, предписывая однакож им предел такой, что ежели что полезное и к лучшему ходу изобретено будет, за то похвалу получить они должны, а напротиву того напрасно употребленные и не к пользе издержки возвращаемы с них будут, как то на других флотах дозволяется, впрочем, коллегия остается на прежних штатах, ибо перемены, учиненные Грейгом, не могут служить всеобщими правилами, так как он и сам изъясняется, что сие взял с примеру и не почитает, чтоб для всех кораблей общественно такия перемены, в разсуждении разности, полезны были».
10 февраля 1769 года коллегия после обсуждения вновь остановилась на решении позволить изменения в конструкции кораблей на страх и риск капитанов. Предложенные Грейгом нововведения еще долго не вошли в широкую практику.
4 мая 1769 года в коллежском присутствии рассматривали вопрос о вентиляторах «для вытягивания дурного воздуха» и заливных трубах, установленных на корабле «Трех Иерархов», и решили сделать по их образцу устройства для кораблей, фрегатов и других судов мирного времени.
В 1768 году моряк встретил Сейру Кук, дочь купца-шотландца Александра Кука, который поставлял канаты для русского флота. Любопытно, что Сейра была двоюродной сестрой Джеймса Кука, знаменитого мореплавателя. 21 августа 1768 года Сейра и Самуил обвенчались в Санкт-Петербурге, в английской церкви. Сейре (в русском обществе ее именовали Саррой) тогда было около шестнадцати лет, Самуилу — тридцать три. Они любили друг друга, и в 1774 году Сарра даже сопровождала моряка, когда он отправился с эскадрой на Средиземное море.
20 января 1768 года Адмиралтейств-коллегия приняла решение о назначении Грейга вновь на «Трех Иерархов». Эту кампанию он провел в Балтийском море, а следующим летом моряк отправился в прославившую его Архипелагскую экспедицию.
11 июля 1768 года реис-эфенди (министр иностранных дел Турции) потребовал отвести русские войска из Подолии и от турецкой границы. Осенью, не получив положительного ответа, правительство султана (диван) объявило войну России. Поводом для нее послужило разорение казаками — русскими подданными приграничных турецких городков Балта и Дубоссары.
В начале 1769 года крымские татары совершили набег на земли Украины, а турецкие войска направились к Днестру, чтобы двигаться далее на Киев и Смоленск. Турки готовили наступление и через Азовское море на Астрахань. Они считали обеспеченным свое положение на Черном и Средиземном морях, где русские суда появлялись редко, однако просчитались.