Born in Warren, Minnesota, Nelson attended St. Olaf College before graduating from University of Minnesota, where he became acquainted with Bob Dylan and co-founded a seminal folk revival magazine, The Little Sandy Review. As a critic, he defended Dylan when he "went electric" at the Newport Folk Festival in 1965 and was instrumental in supporting the careers of Dylan, Clint Eastwood, Leonard Cohen, Elliott Murphy, Willie Nelson, Bruce Springsteen, Jackson Browne, Neil Young, The Ramones, The Sex Pistols and Warren Zevon. While employed by the A&R department of Mercury Records from 1970 to 1975, Nelson briefly served as David Bowie's publicist and championed Rod Stewart, Doug Sahm, Blue Ash & the New York Dolls; he also compiled The Velvet Underground's archival 1969: The Velvet Underground Live and made unsuccessful bids on behalf of the label for Springsteen, The Modern Lovers & Richard and Linda Thompson.
As the record reviews editor of Rolling Stone from 1978 to 1983, Nelson researched long features about Eastwood, Zevon and Ross Macdonald (only an expurgated version of the Zevon piece would see print) while championing a new generation of critics, including Kurt Loder, Charles M. Young and Mikal Gilmore. He frequently quarreled with publisher Jann Wenner over content (under Nelson's aegis, prominent reviews of The Dead Boys, Joy Division, and Public Image Ltd. were published) and length issues, precipitating his eventual resignation.
Although Nelson found transitory employment as a copy editor at The Jewish Week, attempted to write two major pieces on Cohen and Lucinda Williams for LA Weekly in 1993, and continued to sporadically contribute reviews to Musician and People until 1996, he largely recused himself from professional writing following his resignation from Rolling Stone, devoting most of his literary energies to an unfinished screenplay partially set during World War II. A devoted lifelong cinephile with predilections for John Ford's oeuvre and film noir, he was an early adoptee of the videocassette recorder and enjoyed taping obscure exemplars of classic Hollywood cinema. Throughout much of this period, Nelson was employed as a clerk at Evergreen Video, a now-defunct specialty shop in the Greenwich Village neighborhood of Manhattan.
Nelson was found dead in his apartment on the Upper East Side in July 2006. Heart disease was determined to be the cause of death, according to the medical examiner's office in New York City. In a 2011 overview, Charlie Finch of Artnet commented on Nelson's lifestyle choices: "Nelson didn't drink or do drugs: what he did do was eat a hamburger and veal picatta for dinner, always with two Cokes, even for breakfast, while smoking Nat Sherman cigarettes, every day of his adult life."
Nelson was acquainted with the novelist Jonathan Lethem (with whom he shared newfound interests in Philip K. Dick's novels and the music of Chet Baker) in the mid 1980s; the character of Perkus Tooth in Lethem's 2009 novel Chronic City is partially inspired by Nelson. In November 2011, Fantagraphics Books published Everything Is an Afterthought: The Life and Writings of Paul Nelson, by Kevin Avery. Another book edited by Avery, Conversations With Clint: Paul Nelson's Lost Interviews with Clint Eastwood, 1979 - 1983 was published in December 2011 by Continuum Books, with a foreword by Lethem.