Именно тогда впервые проявилось замечательное качество Петра – умение извлекать уроки из ошибок. Из-за границы пригласили видных военных инженеров и фортификаторов. Командование над всеми вооруженными силами на юге вручили опытному воеводе Алексею Семеновичу Шеину. Но самое главное – в верховьях Дона заложили несколько верфей. На самых крупных – в Воронеже, Острогожске и Козлове – на строительстве 22 галер, 4 брандеров и 2 кораблей трудились десятки тысяч работников-крестьян. 13 января 1696 года государь даже издал указ об освобождении от крепостной зависимости тех крестьян, которые запишутся на военную службу под Азов.
В мае того же года русская армия, поддерживаемая теперь флотом, вновь подошла к стенам крепости. 19-го числа галеры Петра и казачьи «чайки» сожгли несколько турецких судов, а 14 июня приблизившиеся к устью Дона 6 турецких кораблей и 17 галер были вынуждены ретироваться без единого выстрела после демонстративного выхода навстречу им русской эскадры. 17 июля иррегулярные формирования царских войск приступили к штурму. А уже на следующий день турки начали переговоры о сдаче. Сильнейшая крепость Османской империи капитулировала. Шеститысячный русский гарнизон вступил под ее своды на полтора десятка лет.
Однако и Петр, и его штаб понимали, что победа 70-тысячной армии над 5-тысячным гарнизоном, да еще лишь со второй попытки, вряд ли может считаться полноценной. Царь начинает первый этап своей военной реформы. В 1698 году, после возвращения из поездки по Европе, он расформировывает все старые полки, кроме четырех, в которые были сведены самые надежные и подготовленные воины, числом 28 тысяч человек. В следующем году начался призыв 32 000 даточных людей – первый рекрутский набор.
Сущность рекрутской системы состояла в следующем. Все податное население России каждый год отдавало одного новобранца с определенного числа душ – сначала 500, а в случае необходимости – 300, и даже со 100 человек. Отданный в рекруты, а также его жена и дети переходили в другое, более привилегированное сословие. Дворянство освобождалось от рекрутской повинности, но не от обязательной военной или гражданской службы. Дворянский недоросль начинал ее в одном из гвардейских полков. Получив через несколько лет чин сержанта, он мог либо перейти в качестве офицера в армейские части, либо продолжать тянуть лямку в гвардии. В условиях Северной войны русская армия испытывала нехватку младшего командного состава. Поэтому нередко офицерские должности занимали выходцы из недворянских сословий – ремесленники, разночинцы, купцы, поповичи, крестьяне. Впоследствии доступ в офицерский корпус низшим сословиям был ограничен.