Многообещающий вингер с хорошей скоростью и высоким Кпд, еси можно так говорить о футболистах, стал частью обмена между Халл Сити и Ливерпулем. "Тигром" в его результате стал Джон Уэлш. До того Пол тренировался с молодежной командой ВБА, которая вскоре не посчитала Андерсона достойным дополнением к своей команде, и юноша перебрался в Халл. После впечатляющей игры за команду Академии "Тигров" Рафа Бенитес принял решение заполучить вингера. Сделка состоялась в январе 2006 года. Андерсон быстро влился в состав и стал ключевым игроком команды, которая в том же 2006 году выиграла молодежный кубок страны. В сезоне 2007-08 он был отдан в годичную аренду в Суонси Сити, где стал лучшим молодым игроком года, забив 7 голов. "Лебеди" по итогам того сезона пробились в Чемпионшип.

В следующем сезоне он, опять же, на правах аренды, выступал за Ноттингем Форест. который, как и Суонси, пробился во второй по силе дивизион. Он выходил на поле в 28 матчах, забил два гола, но во время одной из игр, а точнее, во время кубкового противостояния с Дерби получил ужасную травму - перелом ключицы. Однако руководство клуба полностью устраивала игра Пола, и по итогам сезона "Лесники" сделали "Красным" предложение о покупке вингера. Суонси также не остались в стороне: предложения обоих клубов равнялись приблизительно 250 тысяч фунтов, и выбор был за самим игроком. В конце июня 2009 Пол Андерсон подписал постоянный контракт с клубом Ноттигнем Форест.

В следующем сезоне Пол провел 37 матчей в старой-новой команде, включая также оба полуфинала Плей-офф лиги за выход в элиту, когда "Лесники" по сумме двух матчей проиграли Блэкпулу. Андерсон четырижды отличался в играх Чемпионшипа, а также записал на свой счет один гол Кубка Лиги против Брэдфорд Сити. Летом 2010 Полу исполнилось всего 22 года, и это значит, что лучшие годы в его карьере еще впереди.