Naur begon zijn carrière als astronoom. Hij promoveerde in 1957 aan de Universiteit 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 het Niels Bohr-instituut en de Technische 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 van computerprogramma's en algoritmes. Gebieden zoals software engineering en software-architectuur hadden ook zijn belangstelling. In zijn boek Computing, 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 de A.M. Turing Award voor zijn werk voor Algol 60 en in het bijzonder voor zijn rol als redacteur van het Report on the Algorithmic Language Algol 60, waarin voor het eerst gebruik werd gemaakt van BNF.
Privéleven
Peter Naur was bovendien een amateurfluitist, die jaarlijks aan het ASKOV muziekfestival in Denemarken deelnam. Hij arrangeerde muziekstukken van Chopin voor blazers in kleine bezetting, die hij met andere amateurmusici uitvoerde.