Не видя перспектив роста в английском флоте мирного времени, где шотландцев не жаловали, Грейг решил перейти на иностранную службу. В то время Екатерина II, вступив на престол, готовилась осуществлять грандиозные политические планы. Ей был необходим боеспособный флот. В строю недоставало опытных моряков, их приглашали из-за границы. По поручению Императрицы посол в Англии С. Р. Воронцов подбирал офицеров-мореходов. Грейг принял приглашение и обратился с ходатайством в британское Адмиралтейство. Уже 7 мая 1764 года он получил разрешение поступить на русскую службу. Вскоре Грейг выехал в Россию. 18 июня появился указ о приеме на службу группы офицеров (трое из них были шотландцы). Грейга сразу, через два чина, произвели в капитаны 1-го ранга, но в кампанию 1764 года ему, как и другим иностранцам, для «скорейшего познания обрядов нашей службы», предстояло служить волонтером на эскадре адмирала А. И. Полянского. На подлиннике указа об этом Екатерина II собственноручно приписала:
В 1764 году дублером командира единственного российского 100-пушечного корабля «Святой Дмитрий Ростовский» в эскадре адмирала А. И. Полянского, следующим летом командиром фрегата «Святой Сергий» в эскадре адмирала С. И. Мордвинова Грейг ходил по Балтике. Именно с этого времени он начал вносить свой вклад в совершенствование Российского флота.
Моряк представил Адмиралтейств-коллегии новый способ вооружения военных судов, испытанный им на своем фрегате. Точнее сказать, Грейг не столько придумал нечто новое, сколько предложил ввести на корабли Российского флота то, что уже использовали в практике британского флота.
29 июля 1765 года Грейг докладывал коллегии о сделанных им на фрегате нововведениях. Шканцы удлинили от бизань-мачты к грот-мачте для лучшего расположения людей во время работы на судне. Снасти распределяли так, чтобы «одна от другой лежали свободно, дабы избежать замешательства, ежели случится, что все матросы сбегутся на один палуб, и снасти ходячие не лежали бы одна чрез другую и во время баталии для лучшего употребления мелкаго ружья».
Шпиль сделали двойной, чтобы вращать его можно было с верхней и нижней палуб одновременно; это позволяло поднимать якорь в непогоду, увеличить скорость подъема за счет большего числа моряков, работающих на шпиле. Кроме того, матросы на верхней палубе были готовы работать с парусами, как только якорь оторвется от грунта. Грейг сделал на фрегате мачты короче и реи тоньше, что облегчало работы при постановке парусов, повышало остойчивость судна, и увеличил количество парусов на мачтах.
Для штормовых условий он же предложил уменьшенные паруса: грот, фок и марсели, а для плавания в тихую погоду — увеличенные стаксели, брамсели, грот и фор-марсели. Моряк отмечал, что лично он придумал делать верх фор-марселя, грот-марселя и брамселей с выемкой сверху дугой, чтобы паруса не полоскали; снасти он рекомендовал упростить, уменьшив число блоков.
22 августа 1765 года Адмиралтейств-коллегия приняла решение достраивать один из кораблей с изменениями, предложенными Грейгом. 3 апреля 1766 года Грейга определили командиром на строящийся 66-пушечный корабль, который при спуске назвали «Трех Иерархов». С разрешения Екатерины II моряк оснастил его по-новому, превратив в образец для кораблей и фрегатов. Он сократил высоту мачт, увеличил парусность за счет кливеров, стакселей, ввел четвертый ряд парусов на фок- и грот-мачтах, что повысило остойчивость и скорость, кроме того, увеличена была площадь стакселей и брамселей, изменен покрой парусов для сохранения лучшей формы на ходу, а также расширены были марсы, тоньше и легче сделаны реи, упрощена проводка бегучего такелажа, снято много лишних блоков. К списку усовершенствований моряк добавил следующий комментарий:
«Искусство состоит в опыте или примечании морской практики, отчего всякий корабль может лучше иметь ход, понеже в Англии всякий капитан власть имеет на своем корабле к лучшему ходу во всем перемену делать, и для того де, с самого лучшего в ходу в английском флоте 66-пушечного корабля, по великости онаго, взял он ту препорцию, чему приложил роспись как у нас по штату положено и какую он сделал отмену и прибавку».
В России такая вольность была новинкой, да и англичанам, как оказалось, не все было дозволено делать. Вице-адмирал Г. А. Спиридов, признав полезными нововведения Грейга, отметил, что в Англии, если скорость судна в результате усовершенствования не возрастет, убыток от переделок возлагается на капитана.