Paul Kirchner asistió a la Cooper Union School of Art, pero la abandonó al tercer año, cuando, con la ayuda de Larry Hama y Neal Adams, comenzó a trabajar en la industria del cómic. Escribió historias para la línea de terror de DC y ayudó a Tex Blaisdell en Little Orphan Annie.
En la década de 1970 y principios de 1980, Kirchner hizo varias docenas de portadas para la revista pornográfica Screw. Realizó regularmente ilustraciones para The New York Times, The Wall Street Journal y otras publicaciones. En diciembre de 1973, Ralph Reese le presentó a Kirchner a Wally Wood, para quien trabajó como asistente durante varios años. Y a mediados de esa misma década escribió e ilustró el cómic surrealista Dope Rider para High Times.
Desde 1978 hasta 1985, Kirchner publicó en la edición estadounidense de la revista Heavy Metal unas tiras de entre 6 y 8 viñetas protagonizadas por un hombre que espera el autobús. El humor absurdo y las situaciones surrealistas fueron la norma en estas pequeñas piezas, que más tarde se reunieron en las 96 páginas de un libro de formato apaisado en blanco y negro, titulado The Bus (Ballantine, 1987), publicado en España por Ninth Ediciones en 2014. Kirchner también escribió e ilustró algunas historietas breves ocasionales para Heavy Metal y Epic Illustrated. En sus series los finales suelen ser abiertos y circulares, tendiendo a volver al inicio de la historia generando narrativas en bucle.
En 1981, a través de su hermano Thomas Kirchner, monje budista zen, Paul se reunió con el practicante zen y escritor Janwillem van de Wetering, y juntos produjeron una novela gráfica de detectives, Murder by Remote Control (Ballantine, 1986). También en 1981, codiseñó una línea de figuras de acción militar, Eagle Force, para la Corporación Mego. En 1983-84, Kirchner hizo el arte y los cómics incluidos en el paquete para la línea de juguetes Robo Force de CBS Toys. Desde mediados de la década de 1980 hasta mediados de la década de 1990, escribió y dibujó para las revistas He-Man, GoBots, ThunderCats, GI Joe y Power Rangers, publicadas por Telepictures (más tarde, Welsh Publications). Posteriormente, ilustró caricaturas surrealistas para la revista VQ y la serie de larga duración Jack B. Quick en Sports Illustrated for Kids.
Paul Kirchner dejó de hacer cómics desde mediados de los 90 hasta principios de los 2010. Entre 2013 y 2015 dibujó nuevos episodios de El Bus que se han publicado en varias revistas en los Estados Unidos y en Europa. También relanzó Dope Rider para High Times. Actualmente realiza la tira Hieronymus & Bosch, que aparece en la sección de cómics del sitio web Adult Swim.
Kirchner ha escrito y dibujado diversos libros sobre armas, combate, caza. Ha trabajado en publicidad dirigiendo diferentes campañas como director de arte. Vive en Connecticut con su esposa, Sandy Rabinowitz, una ilustradora especializada en arte equino. Tienen tres hijos.