Paul Rudolph was born in Elkton, Kentucky. He earned his bachelors's degree in architecture at Auburn University (then known as Alabama Polytechnic Institute) in 1940 and then moved on to the Harvard Graduate School of Design to study with Bauhaus founder Walter Gropius. After three years, he left to serve in the Navy for another three years, returning to Harvard to receive his master's in 1947.

He moved to Sarasota, Florida and partnered with Ralph Twitchell for four years until he started his own practice in 1951. Rudolph's Sarasota time is now part of the period labeled Sarasota Modern in his career. Notable for its appearance in the 1958 book, Masters of Modern Architecture, the W. R. Healy House, built in 1950, was a one-story Sarasota house built on posts.

Other Sarasota landmarks by Rudolph include the Sarasota County Riverview High School, built in 1957 as his first large scale project. Currently, it is slated for demolition despite international criticism and a great deal of controversy in Sarasota, where many members of the community are appealing for the retention of the historic building since the decision reached in 2006 by the county school board.

Paul Rudolph's Florida houses attracted attention in the architectural community and he started receiving commissions for larger works such as the Jewett Art Center at Wellesley College. He took over the helm of the Yale School of Architecture as its dean in 1958, shortly after designing the Yale Art and Architecture Building. That building often is considered his masterpiece. He stayed on at Yale for six years until he returned to private practice. He designed the Temple Street Parking Garage, also in New Haven, in 1962.

He later designed the Government Service Center in Boston, the main campus of University of Massachusetts Dartmouth (originally known as Southeastern Massachusetts Technological Institute, and later as the Southeastern Massachusetts University), the Dana Arts Center at Colgate University, and the Burroughs Wellcome headquarters in North Carolina.

While the Brutalist style fell out of favor in the U.S. during the 1970s, Rudolph's work evolved, and became in demand in other countries. Rudolph designed reflective glass office towers in this period, such as the D. R. Horton, and Wells Fargo towers in Fort Worth, which departed from his concrete works. Rudolph continued working on projects in Singapore, where he designed The Concourse office tower with its ribbon windows and interweaving floors, as well as projects in other Asian countries through the last years of his life.

His work, the Lippo Centre, completed in 1987, is a landmark in the area near Admiralty Station of MTR in Hong Kong, and a culmination of Rudolph's ideas in reflective glass. In Indonesia Rudolph pieces of art can be found in Jakarta, Wisma Dharmala Sakti, and in Surabaya, Wisma Dharmala Sakti 2.

Rudolph was fairly open about his sexuality. Yet the extent to which his homosexuality contributed to his exaggeratedly masculine aesthetic can only be speculative. Rudolph's reputation, in decline for some time, is beginning to rise again.

Rudolph died at the age of seventy-eight in New York from mesothelioma, a cancer that almost always originates from exposure to asbestos.