Naur begon zijn carrière alsastronoom. Hij promoveerde in 1957 aan deUniversiteit van Kopenhagen. Toen hij in aanraking kwam met computers veranderde hij van beroep. Van 1959 tot 1969 was hij verbonden aan Regnesentralen, het Deense computerinstituut. Hij gaf ook colleges aan hetNiels Bohr-instituut en deTechnische Universiteit van Denemarken. Van 1969 tot 1998 was Naur professor aan de universiteit van Kopenhagen.
Zijn belangrijkste werk heeft Naur gedaan op het gebied van ontwerp, structuur en prestaties vancomputerprogramma's enalgoritmes. Gebieden zoalssoftware engineering ensoftware-architectuur hadden ook zijn belangstelling. In zijn boekComputing, a human activity (1992), een verzameling van zijn bijdragen aan de informatica, verwerpt hij de formele school van het programmeren die programmeren ziet als een onderdeel van de wiskunde. Naur vond het niet prettig om geassocieerd te worden met BNF en zei dat hij dit liever de Backus Normal Form noemde.
In 2005 kreeg Naur deA.M. Turing Award voor zijn werk voor Algol 60 en in het bijzonder voor zijn rol als redacteur van hetReport on the Algorithmic Language Algol 60, waarin voor het eerst gebruik werd gemaakt van BNF.
Peter Naur was bovendien een amateurfluitist, die jaarlijks aan het ASKOV muziekfestival inDenemarken deelnam. Hij arrangeerde muziekstukken vanChopin voor blazers in kleine bezetting, die hij met andere amateurmusici uitvoerde.