Allen fue a la Washington State University, aunque la dejó 2 años más tarde junto con Bill Gates para perseguir su sueño de escribir software comercial para los nuevos ordenadores personales.
Fundaron Microsoft (inicialmente "Micro-Soft") en Albuquerque, Nuevo México, en 1975, y empezaron vendiendo un intérprete del lenguaje BASIC. Allen fue la punta de lanza de un trato de Microsoft para comprar un sistema operativo llamado QDOS por 50.000 dólares. De esta forma, Microsoft pudo cumplir con su contrato para suministrar el sistema operativo para los nuevos PC de IBM. Fue el principio de un remarcable y constante crecimiento para la nueva compañía exitosa. Sin embargo en 1983 tuvo que dejar Microsoft ya que se le diagnosticó la enfermedad de Hodgkin, que finalmente logró superar.
En 1990 volvió a la empresa ocupando una posición directiva, y ese mismo año creó Vulcan Ventures, un fondo de capital de riesgo especializado en servicios de cable y banda ancha. Y Allen se ha ganado la fama, a través de la firma, de ser uno de los más exitosos inversores de capital en Silicon Valley. Posee participaciones en más de 50 empresas de sectores como el tecnológico y el de entretenimientos, Experience Music Project, Entertainment Properties Inc, Charitable Foundations, Vulcan Ventures Inc, First & Goal Inc y Clear Blue Sky Productions son solo algunas de ellas.
A principios de septiembre del 2000, Paul Allen decidió abandonar completamente Microsoft y todos los cargos que ocupaba. En un emotivo comunicado, firmado por el propio Bill Gates, se reconocía la contribución de Allen al éxito de la compañía. En el futuro ejercerá como consejero estratégico. También, accionarialmente se ha desvinculando del gigante de Redmond. El hombre que en 1976 tenía un 36% de Microsoft, ahora apenas posee el 4%.
