Учреждён в 1698 или 1699 году Петром I и до учреждения в 1714 году ордена Св. Екатерины являлся единственным орденом Российской империи. Первым кавалером ордена стал дипломат Фёдор Головин в 1699 году. Орден был учреждён Петром I 30 августа 1698 года согласно одному свидетельству. В современной литературе указывается 30 ноября как день учреждения ордена, хотя на самом деле эта дата является днём памяти cв. апостола Андрея Первозванного по старому стилю. Предполагается, что Пётр I, только что вернувшийся из Великого посольства, захотел иметь в своей державе орден наподобие тех, о которых он узнал в Англии.
Ученик Иисуса Христа Андрей Первозванный по церковной легенде занимался распространением христианства на территории будущей Руси и считается покровителем России. Он был распят на косом кресте (Андреевский крест) в Греции около 70-го года, что определило дизайн наградных знаков.
Хотя орден стал вручаться, не существовало его официально утверждённого статута. Известен проект статута 1720 года, затем был проект статута 1744 года (содержавший отличия от статута 1720 года), но только в 1797 году при Павле I статут был утверждён и впервые опубликован.
Первым ордена удостоился соратник Петра, граф Фёдор Головин, 20 марта 1699 года, о чём оставил свидетельство И.-Г. Корб, секретарь австрийского посольства. Головин объяснял Корбу содержание статута ордена св. апостола Андрея Первозванного, но до нашего времени этот первоначальный проект Петра I не дошёл. Судя по награждениям, орден выдавался за особые заслуги перед Российским государством, включая как боевые подвиги, так и гражданские отличия.
Знаки ордена Андрея Первозванного состояли из:
Орден Святого Апостола Андрея Первозванного
Портрет А. В. Суворова с голубой андреевской лентой и звездой ордена Св. Андрея Первозванного выше других орденов