The town of Stoneham, previously known as Charlestown End, was incorporated in 1725. A vote in 1726 provided for the building of a 1,440-square-foot meetinghouse however the First Congregational Church itself was not organized until July 1729, with thirteen founding members, when the first church covenant was read and adopted. The first pastor was Rev. James Osgood, a 24 year old Harvard graduate from Salem, who was called in October 1728, and ordained in September 1729. Osgood served until his death in 1746 and was replaced by John Carnes, who was dismissed from his position in 1757. John Searl succeeded Carnes in 1758, followed by the ordination of John Cleaveland Jr. in 1785.

Rev. John Cleaveland Jr. was the son of Rev. John Cleveland of Essex, a separatist minister who served as a chaplain in the French and Indian War and the American Revolution. Cleaveland Jr., unable to pay for a college education, was instead taught by his father. His pastorate at Stoneham was his first ministry. Cleaveland's ministry began amicably. With the opening of the Stoneham Circulating Library, which was kept at the parsonage, Cleaveland became the town’s first librarian. Cleaveland’s relationship with the church’s members remained favorable until the passing of his wife in 1793. Following his wife's death, Cleaveland married Elizabeth Evans, his housekeeper. The reaction to this marriage was negative; at various times Cleaveland found the door to the meeting house nailed shut, the seat of the pulpit covered in tar, and the tail of his horse cut off. While the church itself supported Cleaveland, the town consistently did not, refusing to raise his salary and going so far as to shutter the meeting house so that public worship could not be held there. An ecclesiastical council called late September 1794 dissolved Cleaveland's relationship with the town and church.

Several pastors were called after Cleaveland, and in 1803 the town voted for the construction of a new, larger, meetinghouse. A bell for the new meetinghouse's belfry was purchased in 1810 with money raised through subscription, and a Sabbath-school was established in 1816. The second meetinghouse burned to the ground in 1840. That same year, at the cost of $5,500, the third, and final, meeting house was constructed. An example of Greek Revival architecture, the third meeting house was added to the National Register of Historic Places in 1984.

The First Congregational Church in Stoneham, UCC, continues to serve the local community today.