Born in Cambridge, Massachusetts, Frost graduated from Harvard College in 1907 and launched his career by working for the New York office of Charles Platt, where he assisted with projects such as the Harold McCormick estate in Lake Forest, Illinois. In 1909, Frost became employed by the Olmsted Brothers and focused his attention towards the Boston Metropolitan Park System.
Frost embarked on a European tour in 1912 and was greatly influenced by his encounters with Italian and English gardens. Upon returning to the United States, Frost also spent time viewing the southern plantations along the Ashley River, including the Magnolia Plantation in Charleston, South Carolina.
In 1914, Frost opened an office in Harvard Square where he transitioned away from his early interests in suburban subdivisions and garden city planning and eventually specialized in designing gardens throughout New England. Notable projects include the Judge Seth Gage garden in Weathersfield, Vermont; the Mrs. George W. Pierce garden in Cambridge, Massachusetts; the redesign of Longfellow Park, also in Cambridge; the courtyard of the Chestnut Street Apartments in Boston; and an herb garden for the Jeremiah Lee Mansion in Marblehead, Massachusetts. Perhaps Frost's most characteristic design was his own garden on a small cul-de-sac near Harvard Square, which he designed and cultivated between 1921 and 1953.
Highly knowledgeable about plants, he was a lifelong member of the Massachusetts Horticultural Society and would frequently lecture at the Rhode Island School of Design and the Cambridge School of Architecture and Landscape Architecture. Paul Frost died in Boston on June 21, 1957.