Работы были начаты осенью 1696 года; на следующий год 3 мая на воду было спущено двадцать три галеры и четыре брандера, которые тотчас же были отправлены к Азовскому морю. Во главе этой флотилии на галере Principium, построенной почти целиком им самим, находился капитан Петр Алексеев. На борте других судов за ним следовали: адмирал Лефорт, вице-адмирал Лима, венецианец, и контр-адмирал Валтазар де Лозиер, француз. На этот раз русский флот был создан не на шутку.
Нельзя сказать, чтобы он покрыл себя славой, так же, как сухопутное войско под командой боярина Шеина, вместе с которым он должен был совершить новую попытку взятия Азова. Потешные полки слишком привыкли «потешаться»; стрельцы годились только на осаду дворцов; пушечные выстрелы приводили их в смятение. Под стенами неприступной крепости Петр решал уже их участь.
Вид и приемы всего этого лагеря до прибытия настоящих мастеров своего дела напоминали осаду Трои. Генералы теряли головы, Гордон, самый ловкий из них, тщетно пытавшись пробить брешь, собрал всех офицеров и солдат на военный совет. Один из стрельцов предлагал насыпать холм выше стен крепости и затем засыпать ее оттуда. Владимир Великий прибегал будто бы к этому способу при взятии Херсона. Стратегия Владимира Великого принята была с энтузиазмом, но она лишь слегка напугала турок и вызвала улыбку сожаления на лицах немецких инженеров, приехавших наконец. Петр был очарователен в своем увлечении, своей веселости и юношеской дерзости. Он писал своей сестре Наталье, обеспокоенной опасностями, которым он подвергал себя:
«По письму твоему я к ядрам и пулькам близко не хожу, а они ко мне ходят. Прикажи им, чтоб не ходили; однако хотя и ходят, только по ся поры вежливо. Турки на помочь пришли, да к нам нейдут и чаю, что желают нас к себе».
Но стойкий в своих решениях, Петр все так же был подвержен унынию, так же легко выходил из равновесия. 20 мая, отправившись на рекогносцировку с целью помешать турецким судам подвозить съестные припасы к крепости, Петр при виде их многочисленности быстро отступил со своими галерами. На другой день в 10 часов утра он явился к Гордону мрачный, унылый, ожидающий всяких неудач, но в 3 часа возвратился сияющий: не получив никаких распоряжений, повинуясь только своей храбрости, козаки на своих чайках (легких челноках, сделанных из кожи), летающих по воде как птицы, имя которых они носили, атаковали накануне вечером большие корабли султана и обратили их в бегство, причинив им большие потери. Это был для артиллерии Гордона