In 1851, a man named Cornelius Ahern moved to the village of Florence,and began to seek out other Catholics in the area. He started holding mass in his home, with Father Butler of Covington leading the parishioners. As interest grew, it became clear that a church building was needed. Funds were raised by a number of area priests and parishioners, and a small church was built on Shelby Street. The little frame building was dedicated in 1856 and cost $600.
It could accommodate about 400, and its dimensions were twenty five by forty feet, with a steeple measuring at 30 feet. There was no regular mass for many years, as priests would travel on a circuit, much like other denominations. The first regular pastor at St. Paul's was Father Bent, who began his service in 1874. Father Bent soon added a room to be used as a school, with Miss Murphy as its teacher.
The current location of St. Paul's Parish and school was established in 1904, and has undergone many changes throughout the years. The original frame church on Shelby Street was razed in 1926.