V roce 1976 odborník na šifrování a zastánce soukromí Whitfield Diffie společně s matematikem Martinem Hellmanem zveřejnili kryptografickou techniku veřejných klíčů. Vznikl tak protokol zvaný DH key exchange.
V roce 1977 objevili Ron Rivest, Adi Shamir a Len Adleman další šifrovací systém veřejných klíčů, nazvaný podle jejich jmen RSA. Tito vědci pracovali v té době pro MIT, který tak získal některá autorská práva související s PGP. Americký Národní úřad pro bezpečnost (National Security Agency - NSA) však autorům RSA poradil, aby svoje výsledky raději nepublikovali.
Rovest, Shamir a Adleman nakonec své výsledky publikovali. Jejich článek vyšel např. v Communications of ACM v únoru 1978, vol. 21, no. 2, str. 120-126. Učinili tak předtím, než na svou metodu získali patent (autorská práva), jejichž získání jim blokovala NSA. V USA lze získat autorská práva i po publikaci, ve většině jiných zemí však ne. To je také důvod, proč RSA algoritmus je patentován v USA, ale nikde jinde na světě.
Šifrovací algoritmus IDEA (International Data Encryption Algorithm) byl vyvinut ve Švýcarsku, jeho autoři jsou Xuejia Lai a James Massey. I když IDEA používá symetrické klíče, je používán v PGP jako hlavní šifrovací metoda. RSA, který je pomalejší, je totiž použit pouze na zakódování klíče pro IDEA, v němž je pak zakódována samotná zpráva. IDEA je jednou z mnoha variant symetrického šifrování a zatím není známo, že by byla rozluštěna metodou hrubé síly.
V roce 1991 Phillip R. Zimmermann napsal PGP a dal ho k dispozici svým přátelům. Verze 1.0 však používala kryptograficky slabý algoritmus, který byl v dalších verzích nahrazen. Pro podepisování zpráv byl použit algoritmus vzorkování zprávy MD4, později nahrazený novou verzí MD5. PGP, které bylo vystavené na internetu, se dostalo i mimo území Spojených států.
V roce 1993 se objevila první tzv. mezinárodní verze 2.3. Klíčovou změnou bylo zařazení algoritmu IDEA jako symetrické šifry. Na vývoji se již podíleli autoři z celého světa, Phil Zimmermann působil už pouze jako koordinátor prací.
Zároveň probíhal spor mezi Philem Zimmermannem a RSA, kteří si stěžovali na hromadné porušování autorských práv na jejich implementaci RSA algoritmu. Díky tomu se Zimmermann rozhodl poskytnout PGP pro komerční účely firmě ViaCrypt, která používala vlastní implementaci RSA algoritmu. Firma ViaCrypt byla však v roce 1996 pohlcena firmou PGP, Inc., na jejíž práci se podílel i Phil Zimmermann. PGP, Inc., založena na jaře 1996, stále rozšiřuje spektrum elektronických služeb, které se s pomocí PGP stávají skutečně soukromé.
Spor Zimmermanna s RSA vedl také k tomu, že RSA, Inc., tedy firma vlastnící autorská práva na nejrozšířenější implementaci RSA ve Spojených Státech, knihovnu zvanou RSAREF, uvolnila tuto knihovnu jako free public software pro nekomerční použití na území Spojených států. Od té doby je tedy volně šiřitelná verze PGP poskytovaná ještě stále MIT plně nezávadná na území USA.
Mezitím se PGP stává velice populární a jeho rozšíření se běžně označuje za lavinovité. Myšlenka PGP je jednoduchá, implementace vynikající, dostupnost snadná. PGP získalo několik ocenění, ale především se rychle stalo de-facto standardem pro šifrování a digitální podpisy elektronické pošty na internetu.
Počátkem roku 1998 byla společnost PGP, Inc. převzata společností Network Associates, která pokračovala ve vývoji produktu PGP.
V roce 2002 došlo opět ke změně vlastníka produktů PGP. K 30.3. 2002 společnost Network Associates ukončila vývoj a placené dodávky produktu PGP. Téhož roku nově založená společnost PGP Corporation oznámila podepsání smlouvy o odkoupení celé řady softwarových produktů založené na PGP algoritmu od společnosti Network Associates a v prosinci roku 2002 přišla na trh s novou verzí PGP 8.0.