Кавалерами ордена Андрея Первозванного могли быть не более 12 человек «природных Российских кавалеров», подобные установки соблюдались достаточно долго во время правления Петра Великого. В некоторые годы их было даже меньше 12 человек. Первым кавалером ордена Андрея Первозванного стал Федор Алексеевич Головин — ближайший соратник Петра I, отличавшийся незаурядным умом и выдающимися военными и дипломатическими талантами. Именно он в 1689 году заключил Нерчинский мир о границе между Российским государством и Китаем. Во время первого заграничного путешествия Петра I Ф.А. Головин был занят организацией российского флота: приглашал иностранных офицеров и мастеров, закупал необходимые для строительства флота материалы, отправлял за границу русских учеников. По возвращении в Отечество он встал во главе только что созданного «Приказа Воинских морских дел», одновременно возглавляя и Посольский приказ.
Вторым кавалером ордена стал гетман Мазепа, получивший первую русскую награду из рук самого Петра Великого в феврале 1700 года. После известия об измене Мазепы по приказу разгневанного Петра I «персону (манекен Мазепы) вынесли и, сняв кавалерию, которая на ту персону была надета с бантом, оную персону бросили в палаческие руки, которую палач взяв и прицепив за веревку, тащил по улице и по площади даже до виселицы и потом повесил».
В царствование Петра I орденом Андрея Первозванного были пожалованы 38 человек. В их числе был и валашский Господарь Константин Брынковяну, получивший эту награду — за симпатии к России — тайно и не внесенный даже в официальные списки награжденных. Сам Петр I был отмечен орденом в 1703 году седьмым — за руководство операцией по взятию двух шведских судов в устье Невы. Знаки ордена на царя, имевшего официальный чин капитана бомбардирской роты, возложил первый андреевский кавалер Ф.А. Головин. За Полтавскую битву орденом Андрея Первозванного было награждено сразу четыре человека, в их числе генерал Я. Брюс, командовавший во время боя русской артиллерией. Полученная им звезда сейчас хранится в Историческом музее в Москве.
