Аллен родился в семье преподавательницы Эдны Фей Гарднер и военного Кеннета Аллена, который с 1960 года работал помощником директора библиотечного комплекса Вашингтонского университета. Родители использовали мягкий стиль воспитания. Пол научился читать ещё до школы, с детства любил технику. В четвёртом классе серьёзно занимался химией, в шестом — электроникой. В 1960 году, после 6 класса Пол поступил в самую привилегированную школу Сиэтла «Лейксайд», где на занятиях по программированию познакомился с Биллом Гейтсом. Вскоре недалеко от дома Аллена Computer Center Corporationнабирала людей для тестирования компьютера PDP-10 производства корпорации Digital Equipment. Он и его приятели по школе проводили там всё свободное время. Позже компания Information Service Inc. заказала Полу и троим его друзьям (включая Билла) разработать программу расчёта платёжных ведомостей на языке программирования Кобол; взамен они получали бесплатное рабочее время на PDP-10. Свою компанию они назвали Lakeside Programming Group, но завершить работу не смогли. Позже, когда Пол Аллен учился в колледже, Билл получил работу по обработке информации от компании, изучающей транспортные потоки. Для разработки аппаратного обеспечения понадобился третий компаньон — Пол Гилберт, своё объединение и устройство, для считывания дорожного трафика и составления отчёта для дорожных инженеров, они назвали Traf-O-Data. Название придумано Гейтсом от «jack-o’-lantern» — фонаря-тыквы. Для разработки программы под Intel 8008 пришлось эмулировать его на более мощном компьютере IBM 360. 25 декабря 1972 г. Бад Пемброк, который пригласил Пола и Билла работать на Information Service Inc., позвал их работать в компанию TRW, где разрабатывался большой программный проект для Бонневильского энергетического управления. Устройство Traf-O-Data продавалось с 1972 по 1982 гг. и в итоге на счету компании осталось 794,31 $. В 1974 г. Аллен бросил колледж и устроился в Honeywell.