Уже во время учебы в университете он начал писать, и в 1947 году в журнале «Amasing Stories» («Удивительные истории») был опубликован его первый рассказ «Дети завтрашнего дня» — постатомная история Америки, описывающая попытки наладить жалкое существование рухнувшей цивилизации и ужасные последствия мутаций вследствие радиоактивного облучения.
Очень скоро Пол приходит к выводу, что его призванием является писательский труд, и с 1957 года посвящает себя полностью научной фантастике. В том году он пишет девять рассказов, а в следующем году — свою первую повесть «Хранилище древностей». Еще через год — первичные варианты трех повестей и двадцать два рассказа. А вскоре появляются первые рассказы «Полезотехнической Лиги», которую поначалу он задумывал просто как подражание хайлайновской «Истории будущего».
Пол Андерсон не был ни первым, да и не последним, кто замахнулся расписать будущую историю земной цивилизации, но, пожалуй, мало кто так обстоятельно, с такой дотошностью и упорством создает свою версию оной. Исходным положением в произведениях этой серии является следующее: после освоения техники межзвездных перелетов на Земле начинается эра колонизации внеземных миров, которая протекает подобно колонизации американцами Дикого Запада. С Земли эмигрировали многочисленные группы поселенцев, видящих в колонизации иных миров шанс на лучшую жизнь. Процесс колонизации каждой планеты довольно не прост, требует максимального сосредоточения всех сил. В сложившейся ситуации нет условий для развития науки и культуры. Поэтому когда вымирает поколение отцов-пионеров и на арену выступают новые поколения, у них проявляется явный культурный и технический регресс: великолепная техника, которую использовали отцы-пионеры, постепенно утрачивается, как и прогрессивные общественные структуры, и их место зачастую занимают случайные социальные и культурные модели. Наступает к тому же почти полная изоляция новых миров друг от друга — путешествия среди звезд дороги и рискованны. В результате социальное и культурное развитие колоний останавливается где-то на уровне Средневековья.
Тут надо отметить вот что. Сам писатель считает себя «либералом XVIII века», романтическим поборником прав людей, пытающихся отстоять свою свободу в неравном поединке с государственными бюрократическими структурами. Не случайно, видимо, часто в своем творчестве он обращается к средневековым мотивам, воспевая пасторальную романтическую и свободную жизнь простых людей прошлых веков. Чего стоит прекрасная история о космических крестоносцах, отправившихся в Небеса на корабле пришельцев завоевывать Гроб Господен!
