St. Paul's was first organized in 1846 on Sandy Hill in Perkinsville New York by German settlers who wished to be aligned as neither Catholic nor Methodist, the denominations prevalent in the area at that time. The congregation joined the unionistic "Hartwick Synod" and was served by ministers of varied religious persuasions. Its first minister was Rev. Eggers.

St. Paul's first Lutheran minister was Rev. Strobel who served from 1859 to 1863. It was under his guidance that the settlers in Cohocton resolved to build their own church - "Evangelisch-Lutherische St. Paul's Gemeinde" and became aligned with the Lutheran Synod of Pennsylvania. The church was begun in the spring of 1860, the cornerstone was laid Aug. 31 and the unpainted building dedicated on February 11, 1861. Most of the labor, including the felling of logs, preparation of wood, etc. was done by the members themselves. There is no record of the actual cost of the building as it was evidently done on a cash basis. A constitution was adopted June 2, 1862, pledging the congregation to the entire Bible, Augsburg Confession and Luther's Catechism. (Pastor Strobel served the three congregations of Perkinsville, Dansville and Cohocton, conducting services in Cohocton every second Sunday afternoon, for which he was paid $125 a year. His total salary for 3 churches was $500.)

July 1863, the three congregations hired Rev. W. Haaskarl. When he left after one year, the Cohocton congregation decided to form its own parish, although shared Rev. C. Koerner, the minister serving Perkinsville and Dansville. A mission was established in Corning in 1864.

Rev. Werner was hired as St. Paul's minister, but served only a year. (He answered an ad in "Probst's Zeitschrift" and traveled to Cohocton from Detroit, bringing with him an organ for the church. Rev. Werner's was paid $300 a year as minister and was asked to teach school, although the church did not support it. Students paid 8 or 6 cents per week and parents furnished the fuel. A house was purchased for him for $60 and moved by rollers onto the property.

Pastor M. During served from June 1866 to October 1867. In September 1866, St. Paul's broke its ties with the Hartwick Synod and became affiliated with the German Lutheran Synod of New York, "Steimle'sche Synode", due to the congregation's mostly German membership.

In the summer of 1867, an officer of the Steimle'sche Synode caused an exchange of pastors, and Rev. F.W. Spindler came to St. Paul's. In 1868 Pastor Spindler encouraged two confirmands to embroider a gold cross on black velvet for the pulpit. This embellishment was seen as Roman Catholic by a number of members and not to be tolerated in a Lutheran Church. The unwillingness on the sides to compromise or discuss the issue led to court litigation and the eventual involvement of the Synod. Eventually Pastor Spindler and 30 families left to form a separate church.

Candidate Theolody F. Baarman was called to serve but remained only 5 months.

On Dec. 1 1869, St. Paul's withdrew from the German Lutheran New York Synod and joined the Missouri Synod Dec. 22. Rev. C. Gross, President of the Easter District, advised the congregation to call Rev. Christian A. Weisel of Rome. Rev. Weisel's brother-in-law, Rev. Henry Koch, who later served as Pastor at St. Paul's from 1896 to 1900, performed the installation (Rev. Weisel and Rev. Koch had married sisters of Teacher Paul Th. Buerger, grandfather of Rev. E.J. Buerger, minister at St. Paul's from 1955 - 1969.) Rev. Weisel, serving the Dansville church also, persuaded the congregation to use the Missouri Synod Hymnal and began the practice of "Christenlehre", a doctrinal question-and-answer period held after the sermon for the youth. In the summer, Mr. Franz Sick was sent to Baltimore as the congregation's first representative to the eastern District Synodical Convention. From this convention, the congregation was urged to change its constitution, stipulating that members could not be a member of a secret society. Upon its adoption on April 16, 1871, almost half the congregation left to join the church formed in 1868. In the fall of 1870, the parochial school was reopened, with the congregation giving its support in the form of an increase in the pastor's salary. After the death of his wife in January 1872, Rev. Weisel left Cohocton for Haverstraw NY in October 1872.

Pastor Himmler from Wellsville served as vacancy minister before accepting the call to serve the congregation, but only remained until December 1873.

Pastor John Her was installed February 8, 1874 and served until July, 1879. During this time, the congregation decided to place a Crucifix on the altar, built an addition to the church to be used as the school, and began a mission in Naples. The first Ladies Aid was organized in 1877 but disbanded after a few years. In 1878 the first Mission Festival was observed in Cohocton.

Rev. E.J. Sander was installed February 8, 1880 and remained until May2, 1886 leaving to serve in Otto and Little Valley New York. The practice of a freewill offering was begun and the practice of taxing the members was discontinued. The tradition of a children's Christmas Eve Service was begun. In 1881 the parsonage was remodeled. 4.5 acres were purchased for a cemetery in 1884.

Pastor Nauss served from Fall 1886 to May 1893, and was followed by pastor J.L. Pfeiffer who was install in October. In July 1896 Pastor Pfeiffer resigned due to ill health and died four months later. Pastor Henry Koch served from September 20 1896 to September 9, 1900, but also resigned due to poor health and advancing years.

Rev. William Malte was installed on December 6, 1900 as minister and teacher. He remained until Dec. 10, 1911 when he received a call to Plato N

The Rev. H. Kaufmann was installed as pastor in the spring of 1912 and remained until the spring of 1922. The Ladies Aid was reorganized and became an active part of St. Paul's on April 12, 1917. June 24, the Lutheran Men's club was organized. After Pastor Kaufmann's departure, the time-honored "Christenlehre" came to an end as well as the parochial school.

Rev. P.Th. Rohde from Mendon was called to St. Paul's and installed July 22 1922. He established the Sunday School and Bible Class. Mrs. Rohde established a mixed choir with Miss Lola Neu as organist. Mrs. Rohde served as organist from 1923 until 1937. Ground was broken for a church within the Village of Cohocton on March 22, 1923. The lots were donated by Henry Drum and Edward Drum and stones for the foundation were taken from a quarry on Sick Road. The cornerstone was laid August 12, 1923. The building was dedicated March 2, 1924. German and English services were held on alternate Sundays. Midweek Lenten Services were in English. The old church was sold to the Springwater Grange. In April 1923 the residence on the corner of Shurts Avenue and Maple Avenue was purchased as the parsonage. In 1925, German services were held on only the last Sunday of the month and Saturday School religious instruction for the children of the congregation was inaugurated. From October 1929 to February 1931, Pastor Rohde conducted services in Wellsboro PA on Sunday evenings. Pastor Rohde died in April of 1931.

Pastor Labrenz from Mendon was installed June 28, 1931. He re-established the mission in Corning, which ultimately received its own pastor. The congregation celebrated its 75th anniversary in September 1931 with Rev. W. Malte preaching in German and Rev. F.C. Verwibe, President of the Eastern District, preaching in English. The church's choir loft was rebuilt in 1939 and a new Hammond organ installed. Pastor Labrenz left Cohocton in March 1944 for Immanuel in Buffalo.

On June 11, 1944 Pastor Andrew Maken was installed. In August 1945, the Honor Roll was installed in the Narthex with the names of members who had served in the Armed Forces. Rev. Dr. Walter A. Maier, International Lutheran Hour Speaker and Rev. E.M. Elliott helped celebrate the church's 85th anniversary on September 2, 1945. In April 1947, the parsonage was sold for $6500 and a smaller one, closer to the church, was purchased for $6000. The Lutheran Laymen's League was organized in 1948. Pastor Maken accepted a call to Hop Bottom Pa in April 1949.

Pastor Carl Wyppich was installed June 19, 1949 and remained until April 1955 when he received a call to West Henrietta. Grace Lutheran Mission in Bath was called into being in November 1954.

July 10, 1955 saw the installation of Pastor E.J. Buerger. The Lutheran Women's Missionary League was organized in October 1957. The mission in Bath was turned over to Rev. Lowell hey from Corning in July 1958. Gerard Drum, son of the congregation was ordained July 12, 1959. Pastor Buerger remained until 1969, celebrating his 50th anniversary at St. Paul's.