11 июля 1796 года американские пленники были выпущены на свободу. В сентябре 1796 года американцы согласились передать дею 36-пушечный фрегат в обмен на полугодовую отсрочку для выплаты по мирному соглашению. Только к концу 1797 года правительство Джона Адамса получило возможность частично выполнить условия мирного соглашения с Алжиром. В феврале 1798 года американский агент Джон Барлоу, к большому удивлению дея, передал ему фрегат «Кресцент» и шхуну «Хамдуллах». Бриг «Хасан Башоу» и шхуна «Скйолдбранд», также предназначенные для передачи Алжиру, тем не менее, по-прежнему продолжали находиться на верфях.

Вслед за марокканцами и алжирцами нападения на американские корабли стали совершать и представители других североафриканских государств. Особенно отличились триполитанцы. Паша Триполи Юсуф Караманли, взошедший на престол в 1796 году, не отличался обходительностью. Он убил своего старшего брата Хасана и держал в заточении своего младшего брата Хамета. В обращении с дипломатами он был груб и беспринципен.

В августе 1796 года триполитанские пираты захватили американское корабли «София» и «Бетси». Команды этих кораблей превратились в заложников. Джоэл Барлоу, генеральный консул в Алжире, был уполномочен начать переговоры. Американцы предложили 40 тысяч долларов за освобождение пленников и заключение мира, но поскольку эта сумма была значительно меньше той, которая была заплачена Алжиру, паша отказался. Только когда американцы предложили, в дополнение к денежным выплатам, передать триполитанцам различные морские принадлежности (порох, ядра, корабельный лес и т. п.) на 10 тысяч долларов, паша дал согласие.

Соглашение было подписано 4 ноября 1796 года. Соединённые Штаты согласились выплатить Триполи единовременно 56 тысяч долларов, при этом паша отказался от получения ежегодной дани. Гарантом выполнения мира выступил алжирский дей, который выступал также в роли арбитра при возникновении различных споров.

Четвёртой державой, вступившей в отношения с США, оказался Тунис. Переговоры с этой страной вёл Джозеф Стефан Фимин, французский купец, проживавший в Тунисе и представлявший интересы США. 28 августа 1797 года американский консул Уильям Итон заключил соглашение с Тунисом, которое включало выплату ежегодной дани и подарков на 180 тысяч долларов. Сюда входила поставка 40 морских орудий, 12 тысяч ядер, около 3 тонн пороха и американского брига для тунисского флота. Однако против его ратификации выступил Сенат. В результате в 1799 году переговоры по этому вопросу продолжились.

В 1799 году Соединённые Штаты были всё ещё должны Алжиру 140 тысяч долларов и 150 тысяч Тунису и Триполи. Кроме того, США были втянуты в войну с Францией. Понимая это, правители североафриканских государств вели себя по отношению к американцам весьма высокомерно. Когда в сентябре 1800 года 24-пушечный фрегат «Джордж Вашингтон» под командованием капитана Вильяма Бейнбриджа прибыл в Алжир с очередным платежом, включавшим порох, сахар и кофе, едва не разразился скандал. Новый дей Баба Мустафа приказал Бейнбриджу доставить эти товары в качестве подарка от дея султану в Константинополь. Более того, Бейнбридж был вынужден спустить американский флаг и поднять на своём фрегате флаг Алжира, что было высшей степенью унижения американского флота.

Только опасение, что отказ может привести к возобновлению нападений на американские торговые суда, вынудило Бейнбриджа выполнить требования дея. В докладе военно-морскому секретарю Бейнбридж не скрывал своего возмущения вопиющим оскорблением американского боевого корабля, который впервые в истории должен был обслуживать правителя пиратского государства Тем не менее 19 октября он привёл своё судно в Константинополь. На его борту находилось помимо американского экипажа около сотни пассажиров из числа алжирских дипломатов и военных, а также огромное количество рогатого скота, лошадей, овец, львов, тигров, антилоп, попугаев и около сотни чернокожих рабов.

Однако такое положение дел не могло продолжаться долго. В 1800 году на выборах президента победил Томас Джефферсон, являвшийся сторонником активного противодействия североафриканским пиратам. Одним из пунктов его предвыборной программы было полное освобождение Соединённых Штатов от выплат пиратам и борьба с ними. Это принесло ему успех, и вскоре Джефферсону представился реальный шанс осуществить свои планы.

К началу XIX века Соединённые Штаты уже имели соглашение с четырьмя североафриканскими государствами. С формальной точки зрения заключение соглашений между американцами и североафриканцами должны были ликвидировать возникавшие противоречия, однако в реальности ситуация была иной. Нападения на торговые суда продолжались.

Триполитанский паша, узнав о соглашении, заключённом в Тунисе в 1797 году, заявил, что ему заплатили слишком мало, и начал угрожать началом войны, если ему не будут сделаны аналогичные выплаты. В качестве реального воплощения своих угроз паша приказал своим пиратам нападать на американские торговые корабли.

В июле 1800 года 18-пушечное пиратское судно «Триполино» захватило бриг «Катерин», следовавший из Нью-Йорка в Ливорно с грузом стоимостью 50 тысяч долларов. В октябре того же года паша Триполи освободил команду, поставив Соединённым Штатам ультиматум — увеличить размер ежегодной дани. В противном случае через шесть месяцев Триполи грозило объявить войну США.

Вымогательства продолжались вплоть до февраля 1801 года, когда он в конечном итоге заявил, что немедленно объявит войну США, если не получит 250 тысяч долларов в виде подарка и 50 тысяч долларов ежегодной дани.

Поскольку окончательного ответа он так и не дождался, паша 10 мая 1801 года решился на публичное объявление войны. Американское консульство было закрыто, а флаг спущен. Президент США Томас Джефферсон, только что избранный на свой пост, решительно взялся за ликвидацию этой проблемы. Собрав командный состав флота, президент отдал указания направить две трети всех имевшихся военно-морских сил в Средиземное море для защиты американских интересов. В качестве командующего эскадрой был выбран капитан Ричард Дэйл Выбор его кандидатуры был неслучаен. В период Войны за независимость США он был лейтенантом на борту «Простака Ричарда» под командованием Джона Пола Джонса, знаменитого американского капитана, поэтому ему были знакомы европейские воды. Поскольку в подчинении Дэйла было более одного боевого судна, по правилам тех лет ему было присвоено звание «командор».

Когда Соединённые Штаты вступили в войну на другом континенте, они не имели для этого достаточных сил и средств. К тому времени, если не считать кратковременного конфликта с Францией, американские морские офицеры не имели необходимого боевого опыта, но это мало смущало правительство.

В приказе президента Дэйлу было указано насколько это возможно воздерживаться от активных боевых действий, включая запрет на захват вражеских кораблей и их сохранение в качестве призов. Командирам американских боевых кораблей предписывалось ограничиться защитой торгового судоходства. Таким образом, инициатива офицеров была максимально ограничена. Кроме того, политика по отношению к североафриканским государствам была крайне непоследовательной. В то время как средиземноморская эскадра направлялась для блокады триполитанского побережья, фрегат «Джордж Вашингтон» направлялся в Алжир с грузом корабельной древесины и других морских припасов на сумму 30 тысяч долларов, которые являлись очередным платежом дани за безопасность мореплавания.