Родился в Бристоле, штат Пенсильвания, в семье выходцев из Скандинавии (чем и объясняется нетипичное для орфографии английского языка написание его первого имени - Poul). Окончил университет штата Миннесота со степенью бакалавра по физике. Второе образование Андерсона- историческое. Кроме того, благодаря своему происхождению, он хорошо знает скандинавские языки (как древние, так и современные) и литературу европейского Севера.
Первая публикация состоялась в 1947 году в журнале "Astounding Science Fiction" (рассказ "Дети завтрашнего дня", написанный в соавторстве с Ф. Н. Уолдропом).
Среди наиболее известных произведений Андерсона - романы "Сломанный клинок" (1954), "Крестовый поход в небеса" (1960), "Танцовщица из Атлантиды" (1971), "Миллионолетний челн" (1989), пенталогия "Звездные нивы" (1993-1999). Русскому читателю лучше всего известен цикл "Патруль времени" (1960,1990).
За полвека творческой деятельности Пол Андерсон семь раз становился лауреатом премии "Хьюго" (1961 - рассказ "Самое долгое путешекствие", 1964 - повесть "Нет мира королям", 1969 - рассказ "Причащение плоти", 1972 - повесть "Царица ветров и тьмы", 1973 - рассказ "Певец", 1979 - рассказ "Охотничья луна", 1982 - повесть "Сатурналии"); трижды получал премию "Небьюла" (1971 - повесть "Царица ветров и тьмы", 1972 - рассказ "Певец", 1981 - повесть "Сатурналии"). Помимо этого, удостаивался премии "Гэндальф" (1978) и премии издательства "Макмиллан" за лучший детективный роман года (1959).
Кроме научной фантастики, пробовал свои силы в таких литературных жанрах, как детективный и авантюрный романы, историческая хроника, фэнтези, произведения для детей, - и, как правило, небезуспешно.
Живет с семьей - женой Карен (несколько раз выступала соавтором мужа - в частности, в тетралогии "Король Иса" (1988), дочерью и зятем, известным фантастом Грегом Биром - в собственном доме в Калифорнии.