Cohen was born in Long Branch, New Jersey, into a Jewish family. He graduated in 1950 from Stuyvesant High School in New York City. Cohen next studied at the Brooklyn College from 1950 to 1953, but he left before earning his bachelor's degree when he learned that he could start his graduate studies at the University of Chicago with just two years of college. At Chicago, Cohen completed his master's degree in mathematics in 1954 and his Doctor of Philosophy degree in 1958, under supervision of the Professor of Mathematics Antoni Zygmund. The subject of his doctoral thesis was Topics in the Theory of Uniqueness of Trigonometric Series.

Cohen is noted for developing a mathematical technique called forcing, which he used to prove that neither the continuum hypothesis (CH), nor the axiom of choice, can be proved from the standard Zermelo–Fraenkel axioms (ZF) of set theory. In conjunction with the earlier work of Gödel, this showed that both of these statements are logically independent of the ZF axioms: these statements can be neither proved nor disproved from these axioms. In this sense, the continuum hypothesis is undecidable, and it is probably the most widely-known example of a natural statement that is independent from the standard ZF axioms of set theory.

For his result on the continuum hypothesis, Cohen won the Fields Medal in mathematics in 1966, and also the National Medal of Science in 1967. The Fields Medal that Cohen won continues to be the only Fields Medal to be awarded for a work in mathematical logic. Cohen was also awarded the Bôcher Memorial Prize in mathematical analysis in 1964 for his paper "On a conjecture by Littlewood and idempotent measures".

Cohen was a professor at Stanford University, where he supervised Peter Sarnak's graduate research, among those of other students.

Angus MacIntyre of the University of London stated about Cohen: "He was dauntingly clever, and one would have had to be naïve or exceptionally altruistic to put one's 'hardest problem' to the Paul I knew in the '60s." He went on to compare Cohen to Kurt Gödel, saying: "Nothing more dramatic than their work has happened in the history of the subject." Gödel himself wrote a letter to Cohen in 1963, a draft of which stated, "Let me repeat that it is really a delight to read your proof of the ind[ependence] of the cont[inuum] hyp[othesis]. I think that in all essential respects you have given the best possible proof & this does not happen frequently. Reading your proof had a similarly pleasant effect on me as seeing a really good play."

While studying the continuum hypothesis, Cohen is quoted as saying that he "had the feeling that people thought the problem was hopeless, since there was no new way of constructing models of set theory. Indeed," he said in an interview in 1985, "they thought you had to be slightly crazy even to think about the problem."

An "enduring and powerful product" of Cohen's work on the Continuum Hypothesis, and one that has been used by "countless mathematicians" is known as forcing, and it is used to construct mathematical models to test a given hypothesis for truth or falsehood.

Shortly before his death, Cohen gave a fascinating lecture describing his solution to the problem of the Continuum Hypothesis at the Gödel centennial conference, in Vienna 2006. A video of this lecture is now available online.