Первое определенное упоминание в документах о Походной канцелярии относится к 1702 г. В это время царь отправился «в поход» в Архангельск. В поездке его сопровождал и начальник продолжавшего существовать Посольского приказа, первый министр Ф. А. Головин. Несмотря на то, что все государственные дела продолжали проходить через Посольский приказ, а «печатанье государственной печатью грамот» должно было далее находиться под контролем бояр, «которым Москва приказала», наиболее важные дела уже решались в Архангельске у Петра Великого. Туда же, в место пребывания царя и его первого министра, был перенесен и центр управления иностранной частью Приказа. В 1705 г. в Походной канцелярии уже присутствуют: тайный секретарь (П. П. Шафиров), два переводчика, два подьячих малороссийского приказа, «да по вся годы посылаются в Свейский (шведский. — Т. С.) поход старый подьячий Василий Степанов и три молодых».
К 1710 г. Походная посольская канцелярия окончательно обосновывается в Петербурге и из временного учреждения обращается в постоянное, причем с 1709 г. ее называют просто Посольской канцелярией. Именно здесь теперь сосредоточивается вся работа по зашифрованию и расшифрованию переписки Петра и его приближенных с различными корреспондентами, а также по созданию шифров и рекомендаций по их использованию.
В период между 1710 и 1718 гг. эта Канцелярия становится главным органом внешних сношений России. Компетенция ее расширяется в ущерб оставшемуся в Москве Посольскому приказу. Растет личный состав Канцелярии. В 1709 г. граф Г. И. Головкин, заступивший место Ф. А. Головина, назначается государственным канцлером, а П. П. Шафиров — вице–канцлером. Именно эти первые лица государства руководят деятельностью постепенно обретающей опыт криптографической службы. Канцлер и вице–канцлер дают указания о создании новых шифров, замене устаревших, по обеспечению шифрами корреспондентов — дипломатов, военачальников, других государственных деятелей. Непосредственно им докладываются отчеты о создании новых шифров, о добыче шифров иностранных. Руководство криптографической службой со стороны канцлера и вице–канцлера вошло в традицию в России, которая сохранялась почти на протяжении полутора веков.
Имена первых руководителей криптографической службы России мало знакомы современному читателю. Между тем все эти люди были выдающимися государственными деятелями, чьи труды на благо Отечества по достоинству ценили современники. Именно их самоотверженное служение государственным интересам позволило Петру Великому выделить этих своих сподвижников среди прочих и поставить на самый верх государственной иерархической лестницы.
Указом от 18 февраля 1700 г. во главе Посольского приказа и принадлежавших к нему приказов был официально поставлен выдающийся деятель и дипломат раннего периода петровского времени Федор Алексеевич Головин (1650—1706). Он сменил здесь думного дьяка Е. И. Украинцева, который в 1699 г. был отправлен послом в Константинополь на русском корабле, впервые явившемся в водах Босфора. При своем назначении Головин получил звание «начального президента государственной посольской канцелярии». Как генерал–адмирал Головин одновременно управлял флотом, возглавлял оружейную палату, монетный двор, малороссийский приказ. Кроме личного участия в переговорах с иностранными государствами и заключения договоров с ними, Головин руководил деятельностью русских послов за границей, оказывал большое влияние на внешнюю политику России в период Северной войны. Под непосредственным наблюдением Головина работало цифирное отделение.
Знатность рода, образованность, недюжинные способности помогли ему занять высший государственный пост. Ф. А. Головин приобрел известность в 1689 г. заключением Нерчинского договора с Китаем. Под Азовом мы видим его в чине генерала наряду с иностранными сотрудниками царя Лефортом и Гордоном. В 1697 г. Головин был уже одним из ближайших сподвижников Петра I, пользовался его большим доверием и расположением. Впервые отправляясь за границу, царь назначил его вторым после Лефорта полномочным послом со званием «генерала, воинского комиссария и наместника сибирского». После смерти Лефорта Головин получил звание генерал–адмирала, в тот же период при учреждении 10 марта 1699 г. ордена Св. Андрея Первозванного он был пожалован первым его кавалером. 16 ноября 1702 г. первым из русских получил графское Римской империи достоинство. Умер Ф. А. Головин 2 августа 1706 г. на пути в Киев, в Глухове. О смерти его Петр I так извещал Ф. М. Апраксина: «Сей недели господин адмирал и друг наш от сего света отсечен смертью в Глухове; того ради извольте которые приказы (кроме Посольского) он ведал, присмотреть и деньги и прочия вещи запечатать по указу. Сие возвещает печали исполненный Петр».