Allen died Monday from complications of non-Hodgkin's lymphoma, according to a statement from Vulcan Inc. on behalf of the Allen family, Vulcan Inc. and the Paul G. Allen Network.
"Paul Allen's contributions to our company, our industry and to our community are indispensable. As co-founder of Microsoft, in his own quiet and persistent way, he created magical products, experiences and institutions, and in doing so, he changed the world. I have learned so much from him - his inquisitiveness, curiosity and push for high standards are something that will continue to inspire me and all of us at Microsoft.
"Our hearts are with Paul's family and loved ones. Rest in peace," said Microsoft CEO Satya Nadella.
Billionaire Allen left Microsoft in 1983 following a dispute with Gates.
He was directing more than $1 billion to philanthropic projects, developing Seattle's South Lake Union tech hub that Amazon.com calls home and building the headquarters of his Allen Institute for Brain Science there.
Paul Gardner Allen was two years older than Gates but when they met in the computer room at the exclusive Lakeside School in Seattle in 1968, they discovered a shared passion.
In 1975 the two jointly developed BASIC software for the Altair 8800, a desktop computer that cost $400 in kit form.
It was Allen's idea to call it Micro-Soft, an amalgam of microcomputer and software. The hyphen was later dropped.