Когда стало известно, что на Павла готовится покушение, римляне срочно перевели его в Кесарию Приморскую, где после вхождения Иудеи в состав Римской империи находилась резиденция римского наместника. Там Павел должен был содержаться под надежной охраной. Прокуратор Феликс был человеком, попавшим «из грязи в князи». Некогда вольноотпущенник, он, благодаря тому что его брат стал фаворитом римских императоров Клавдия и Нерона, добился неслыханно высокого для бывшего раба поста: сначала он занимал важную должность в Самарии, а затем, в 52 г., стал прокуратором Иудеи. Он был трижды женат, и каждый раз на женщинах царского происхождения. Так, например, одна из его жен была дочерью Юбы Мавританского и внучкой Марка Антония и Клеопатры, а третья, Друзилла, дочерью Ирода Агриппы I. Феликс хорошо относился к своему узнику, он не сомневался в его невиновности, но, будучи человеком корыстолюбивым, не отпускал Павла на свободу, рассчитывая получить от него взятку.

Так прошло два года, Феликс лишился должности после того, как видные жители Кесарии подали на него жалобу императору на крайнюю жестокость, проявленную им при подавлении стычек между евреями и язычниками. В 58 или 60 г. его сменил сухой, педантичный, но честный прокуратор Фест, и враги Павла решили воспользоваться ситуацией, понимая, что новый чиновник не захочет сразу же обострять отношения с местным населением. Но Фест был истинным римлянином: хотя он и желал расположить к себе местную элиту, но не собирался становиться игрушкой в их руках. В Кесарию прибыли представители Синедриона, но их обвинения не показались прокуратору достаточно обоснованными.

Павел, понимая, что рано или поздно либо прокуратор уступит давлению, либо его убьют заговорщики, прибег к последнему средству: он был римским гражданином и имел право в случае, если ему угрожал смертный приговор, потребовать личного суда императора. Ему также представился случай защищать себя и свою деятельность перед Иродом Агриппой II. Это был сын Ирода Агриппы I и правнук Ирода Великого, с 44 по 70 г. он управлял северо-восточными областями Палестины и имел титул царя, хотя не обладал реальной властью. Его сестра Берника (в другом варианте произношения Береника) позже чуть было не вышла замуж за римского императора Тита. Тит был в нее безумно влюблен, но когда Берника переехала в Рим и стала открыто жить с императором, население Рима пригрозило Титу, что свергнет его, если он женится на этой женщине, и ему пришлось с ней расстаться. Павел сумел убедить царя в своей невиновности, но так как он потребовал суда императора, он должен был отправиться в Рим. Конечно, Фест мог оправдать Павла, но этим он испортил бы окончательно отношения с Синедрионом. Согласно свидетельству Иеронима, Фест умер в 60 году, так что Павел должен был отправиться в Рим до его смерти. Обычно предполагается, что это 60 год.