Впечатляющая победа при Панорме позволила римлянам овладеть стратегической инициативой и повести наконец наступление на те немногочисленные сицилийские города, которые все еще оставались под контролем карфагенян. К тому времени это были располагавшиеся на юге острова Эрикс, Дрепан и Лилибей, из которых последний был важнейшей пунийской военно-морской базой. Для карфагенян этот город был замковым камнем в системе обороны африканского побережья, и, следовательно, оказавшись в руках римлян, он стал бы ключом для переноса войны в Ливию. Это объясняет как то, почему пунийцы так упорно стремились удержать Лилибей в своих руках, так и то, почему римляне приняли решение ударить в первую очередь именно по нему. Для этого следовало возобновить боевые действия на море, поскольку осада или штурм Лилибея были возможны лишь при одновременных согласованных действиях военного флота и сухопутной армии. С этой целью в 250 г. до н. э. к городу были направлены 200 кораблей и войско во главе с консулами Гаем Атилием Регулом Серраном и Луцием Манлием Вульсоном Лонгом. Все римское войско, по сообщению Диодора Сицилийского, насчитывало 110 тыс. воинов, тогда как гарнизон Лилибея под командованием Гимилькона состоял всего из 7 тыс. пехотинцев и 700 всадников (Diod. XXIV, 1, 1). В таких условиях пунийцам оставалось рассчитывать на крепость городских укреплений и помощь извне, а римлянам следовало отрезать город от внешнего мира и планомерно разрушать крепостные стены.
Римские полководцы повели осаду Лилибея по всем правилам осадного искусства, одновременно блокируя город с суши и с моря. На подступах к пунийской твердыне римляне обустроили два постоянных лагеря, между которыми был прокопан ров, насыпан вал, а на нем установлен частокол. Это позволяло полностью отрезать город от сухопутного сообщения, а вход в городскую гавань блокировали многочисленные римские боевые корабли. Одновременно под крепостные укрепления были подведены стенобитные орудия, позволившие, несмотря на яростное сопротивление защитников, разрушить одну за другой семь приморских башен Лилибея. Гимилькон организовал грамотную оборону – на месте обрушенных стен оперативно сооружались новые, из города делались подкопы под осадные машины, а во время многочисленных дневных и ночных вылазок отряды карфагенян пытались поджечь возведенные римлянами сооружения. Решив после обрушения седьмой башни, что час для штурма настал, консулы повели отряды на приступ полуразрушенных приморских укреплений, но дважды были остановлены и отброшены благодаря умелому командованию Гимилькона и мастерству эллинских наемников. Не удалось полностью отрезать город от морского сообщения – искусные пунийские мореходы на нескольких быстроходных судах стремительно проплывали мимо неповоротливых римских кораблей и доставляли в Лилибей необходимые припасы, поддерживая сообщение с основными силами карфагенского флота, стоявшими в гавани Дрепана, и даже с самой пунийской столицей.
Осада затянулась на месяцы, и ни одна из сторон не имела решающего преимущества. Первым шанс склонить переменчивую военную фортуну на свою сторону представился римлянам – в Лилибее созрел заговор части вождей наемников, собиравшихся сдать город неприятелю. Будучи уверенными, что подчиненные последуют за ними, заговорщики тайно отправились в лагерь римлян, чтобы там обсудить с римскими военачальниками условия капитуляции. Однако о заговоре стало известно Гимилькону, который решил действовать на упреждение и отправил в отряды наемников верных себе командиров, пользовавшихся уважением среди рядовых воинов. К эллинам первым обратился узнавший и доложивший о заговоре ахеец Алексон, к кельтам – Ганнибал, сын того самого Ганнибала, который некогда проиграл сражение при Милах и затем был казнен на Сардинии. Обещая от имени командующего гарнизоном щедрое вознаграждение, они смогли убедить воинов сохранить верность Карфагену, и когда изменники явились к городским стенам с предложением открыть ворота и сдать Лилибей римлянам, то получили в ответ лишь брань и насмешки. Под градом камней и стрел предатели вынуждены были бежать (Polyb. I, 43, 1–8).