В 1667 царь Алексей Михайлович Романов издал указ о создании кораблей для посылок из Астрахани на Хвалынское море. Строительство первого русского военного корабля велось в селе Дединово Коломенского уезда. Для обучения основам кораблестроения были приглашены мастера из Голландии, а по округе собрано 30 плотников, 4 кузнеца и 4 пушкаря. Руководил строительством боярин А. Л. Ордин-Нащокин – инициатор создания флотилии.

Корабль был заложен 14 ноября 1667 года. Параллельно с ним строились яхта, бот и 2 шнявы. Однако гордостью строителей был всё же трехмачтовый малый фрегат, длина которого составляла 24,5 метра, ширина — 6,4 метра, а осадка — 1,5 метра. 24 апреля 1669 г. был издан царский указ о присвоении фрегату названия «Орел» в честь русского государственного герба. На корме фрегата был помещен герб — двуглавый орел, а на мачтах впервые поднят бело-сине-красный флаг.