Переговоры продолжил Дэвид Хэмфри, который в сентябре 1793 года получил от Госдепартамента инструкции о проведении дипломатической миссии. К тому времени ситуация с американскими пленниками весьма обострилась. В сентябре 1793 года Португалия заключила соглашение с Алжиром, и пиратские корабли получили право свободного прохода через Гибралтарский пролив. Это самым пагубным образом отразилось на безопасности американской морской торговли. 25 октября 1793 года алжирские пираты захватывают американский бриг «Полли», а в конце ноября ещё 10 американских кораблей. Общее число захваченных американских граждан составило 119 человек.
Сообщение о нападениях на беззащитные торговые суда вызвало волну возмущения в Конгрессе. В начале 1794 года он наконец выделил средства для строительства шести тяжёлых фрегатов и переоборудования десяти мелких судов для защиты американской торговли. Однако три из шести фрегатов — «Конституция», «Консгеллейшн» и «Юнайтед Стейтс» — были спущены лишь 1797 году.
Наряду с наращиванием военных сил правительство США вновь попыталось разрешить ситуацию дипломатическими средствами. Хэмфри снова был направлен для переговоров с деем. Его помощником стал Джозеф Дональдсон-младший. В апреле 1795 года они отплыли в Европу. Хэмфри остался в Париже, а Дональдсон направился в Алжир. В результате переговоров сумма была снижена до 600 тысяч долларов, и 5 сентября 1795 года обе стороны пришли к мирному соглашению.
Соглашение было подписано Хэмфри 28 ноября 1795 года и ратифицировано Сенатом 2 марта 1796 года. Договор предусматривал выплату значительной суммы, составившей в общей сложности 642 500 долл. Кроме того, США согласились выплачивать ежегодную дань в размере 21 600 долл. Прочие условия соглашения в целом повторяли условия договора США с Марокко.
К сожалению, договорённость не была полностью исполнена, поскольку дей потребовал за освобождение пленников дополнительных подарков на 200 тысяч долларов и немедленного перечисления большей части суммы. При этом часть суммы должна была быть выплачена различными корабельными запасами (порохом, ядрами, корабельным лесом и т. п.), бригом и двумя шхунами. Эти подарки с учётом основной суммы по соглашению составили бы почти миллион долларов, или почти 16 % национального дохода США Выплаты пиратам, таким образом, стали бы самыми крупными в государственном бюджете и потому были неподъёмными для национальных финансов. Несмотря на неспособность выплатить требуемую сумму, 6 марта 1796 года Конгресс ратифицировал договор и немедленно приступил к сокращению военно-морских расходов. Поскольку с Алжиром был заключён мир, президент посчитал, что необходимости в наращивании морских вооружений нет. Конгресс разрешил достроить только три из шести заказанных фрегатов: двух 44-пушечных тяжелых фрегатов «Юнайтед Стейтс» и «Конституция» и 36-пушечного фрегата «Консгеллейшн».
11 июля 1796 года американские пленники были выпущены на свободу. В сентябре 1796 года американцы согласились передать дею 36-пушечный фрегат в обмен на полугодовую отсрочку для выплаты по мирному соглашению. Только к концу 1797 года правительство Джона Адамса получило возможность частично выполнить условия мирного соглашения с Алжиром. В феврале 1798 года американский агент Джон Барлоу, к большому удивлению дея, передал ему фрегат «Кресцент» и шхуну «Хамдуллах». Бриг «Хасан Башоу» и шхуна «Скйолдбранд», также предназначенные для передачи Алжиру, тем не менее, по-прежнему продолжали находиться на верфях.
Вслед за марокканцами и алжирцами нападения на американские корабли стали совершать и представители других североафриканских государств. Особенно отличились триполитанцы. Паша Триполи Юсуф Караманли, взошедший на престол в 1796 году, не отличался обходительностью. Он убил своего старшего брата Хасана и держал в заточении своего младшего брата Хамета. В обращении с дипломатами он был груб и беспринципен.
В августе 1796 года триполитанские пираты захватили американское корабли «София» и «Бетси». Команды этих кораблей превратились в заложников. Джоэл Барлоу, генеральный консул в Алжире, был уполномочен начать переговоры. Американцы предложили 40 тысяч долларов за освобождение пленников и заключение мира, но поскольку эта сумма была значительно меньше той, которая была заплачена Алжиру, паша отказался. Только когда американцы предложили, в дополнение к денежным выплатам, передать триполитанцам различные морские принадлежности (порох, ядра, корабельный лес и т. п.) на 10 тысяч долларов, паша дал согласие.
Соглашение было подписано 4 ноября 1796 года. Соединённые Штаты согласились выплатить Триполи единовременно 56 тысяч долларов, при этом паша отказался от получения ежегодной дани. Гарантом выполнения мира выступил алжирский дей, который выступал также в роли арбитра при возникновении различных споров.