Весной 69 года, после восстания в Кесарии, Феликс был отозван в Рим и попал в опалу. Влияние брата спасло Феликса от наказания — его не принудили к самоубийству, но он никогда больше не занимал общественных должностей. Перед отъездом он легко мог освободить Павла, но не сделал этого, не желая рвать последние полезные связи с иудейскими старейшинами. По крайней мере, он не хотел давать им повода обвинить его перед императором в неоправданных действиях. Осторожный до конца, он оставил Павла в заключении.
Новым прокуратором Иудеи стал Порций Фест, человек более высокого происхождения и более высоких принципов. Напряженные попытки навести порядок в беспокойной провинции подорвали его здоровье — он умер на посту через два года.
Как только бразды правления перешли к нему в июле 59 года, Порций Фест выехал из Кесарии в Иерусалим. Случайно, среди обсуждения многих других проблем, первосвященник поднял вопрос о Павле. Члены синедриона решили, что новый прокуратор захочет произвести благоприятное впечатление, и просили его начать суд над Павлом побыстрее, в Иерусалиме: сорок молодых фанатиков, поспешившие поклясться не есть и не пить, пока не убьют Павла, ждали случая смыть с себя позор и наверняка попытались бы напасть на Павла по пути в Иерусалим. Фест разрушил их планы, хотя и непреднамеренно. Отказавшись проводить суд в Иерусалиме, он велел старейшинам явиться в Кесарию: просто, чтобы не причинять себе лишних хлопот. Он обещал им не откладывать слушания.
Через восемь или десять дней Фест вместе со своими чиновниками и офицерами вернулся в Кесарию и на следующее же утро приступил к обязанностям Верховного Судьи провинции. Дело Павла рассматривалось первым. Когда Павел вошел в помещение суда, иерусалимские иудеи готовы были наброситься на него в ярости — столько злобы накопилось в них за два года; но в присутствии прокуратора они не посмели выражать свои чувства иначе, как злобными выкриками. Фест позднее говорил царю Иудеи: "Обступивши его, обвинители не представили ни одного из обвинений, какие я предполагал; но они имели некоторые споры с ним о Богопочитании и о каком-то Иисусе умершем, о Котором Павел утверждал, что Он жив". Позже иудеи все же представили обвинения, вроде тех, которые сочинил Тертулл, но не смогли вызвать свидетелей. Лука пишет, что Фест выслушивал обвинение за обвинением и просил доказательств, но доказательств не было.
Павел попросту отрицал всякий состав преступления: "Я не сделал никакого преступления ни против закона Иудейского, ни против храма, ни против кесаря".
Фест видел необоснованность обвинений. Но он не разбирался в религиозных вопросах и боялся оскорбить своих новых подданных. Он вспомнил о просьбе синедриона: "Хочешь ли идти в Иерусалим, чтобы я там судил тебя в этом?" — спросил он Павла.
Павел знал, что даже если ему удастся в живых добраться до Иерусалима, там найдут способ от него избавиться. Но иудеи сами допустили ошибку: если бы их обвинения ограничивались рамками нарушения храмовых правил и религиозных обычаев, они могли бы добиться перенесения суда в Иерусалим, и Фест не смог бы помочь Павлу. Но обвинения были слишком широко сформулированы — Павла объявляли во всемирном вредительстве, его называли язвой общества. Политическое обвинение, также как и религиозное, грозило смертной казнью, но Павел решил придать делу скорее политический оттенок, чтобы суд оставался в пределах римской юрисдикции.
Без колебаний Павел ответил Фесту: "Я стою пред судом кесаревым, где мне и следует быть судиму; Иудеев я ничем не обидел, как и ты хорошо знаешь. Ибо, если я не прав и сделал что-нибудь достойное смерти, то не отрекаюсь умереть; а если ничего того нет, в чем сии обвиняют меня, то никто не может выдать меня им; требую суда кесарева".
Выслушав такое формальное требование, Фест стал советоваться со своими приближенными. Любой римский гражданин имел право апеллировать к императорскому суду, но прокуратор должен был решить, достаточно ли серьезно дело, чтобы передавать его в высший суд.
Требование Павла, неожиданное для Феста, не было внезапным решением для самого апостола. У него было два года, чтобы обдумать свой следующий шаг. Он должен был ехать в Рим, так или иначе. И теперь представлялась возможность. Кроме того, решение Галлиона, официально признавшего христианское вероисповедание, могло потерять свою силу: другой чиновник мог отменить его. Единственным выходом из положения было попытаться добиться положительного решения в высшем, императорском суде. Да, императором был Нерон. Но в 59 году он был еще молод и, несмотря на сомнительный путь к власти, оставался другом брата Галлиона, Сенеки, и прислушивался к его советам — а Сенека был умным человеком. Ни Павел, и никто другой не мог предсказать в 59 году, что со временем Нерон превратится в ужасного тирана, само имя которого станет синонимом распущенности и садизма, жестокости и коррупции. Апелляция к императорскому суду требовала больших расходов, но Павел не тревожился. Бог всегда давал ему все необходимое — и тогда, когда запросы его были ничтожны, и теперь. Вполне возможно, что Павел получил наследство, оставшееся после отца, как единственный живой наследник по мужской линии.