Dooley was born Paul Brown in Parkersburg, West Virginia, the son of Ruth Irene (née Barringer), a homemaker, and Peter James Brown, a factory worker. He has said that Parkersburg had few attractions that interested him; there were no theaters or cultural opportunities, and his family had no television set. He enjoyed listening to comedians on the radio, especially Jimmy Durante. Dooley was a cartoonist as a youth and drew a strip for a local paper in Parkersburg. He joined the United States Navy. Dooley then returned home and graduated from West Virginia University in 1952.
After graduating from West Virginia University, Dooley went to New York City to try his luck in the entertainment industry. He initially found work as a clown for children's birthday parties. In New York he soon found success as a regular on the stage. In the early 1950s, he made his debut on the New York stage and was discovered by Mike Nichols. The director gave him his first break by casting him in 1965's The Odd Couple on Broadway. Dooley played a poker buddy and understudied Art Carney, who played Felix Unger. Eventually when Carney left the play Dooley got the part. He got an agent at William Morris Agency thanks to a referral from Walter Matthau, who played Oscar Madison in the play.
Also having an interest in comedy, Dooley was a stand-up comedian for five years, eventually landing on The Tonight Show, and a member of the Compass Players and The Second City troupe in New York City. Fellow members of The Second City at that time were Alan Arkin and Alan Alda. Dooley also worked as a writer. He created and was one of the head writers on The Electric Company, produced by the Children's Television Workshop (now called Sesame Workshop) for PBS in the United States. Dooley wrote "runners", a series of short sketches with 8 or 10 characters that were broadcast over the course of several weeks. He found out years later that Carl Reiner had recommended him for the job. Dooley formed a company with Andrew Duncan and Lynne Lipton called All Over Creation to create commercials for radio and television. They produced around 500 TV commercials and 1,000 radio spots. A character named Paul the Gorilla that appeared in television commercials was named after him.