The parish was founded in 1873 when Rev. John Stephen Michaud became its first resident pastor. For several years, he celebrated mass in a schoolhouse. In 1875, he purchased some land on a hillside overlooking the lake. Shortly after, the first St. Mary's was built on Pleasant Street, in what was then Newport Village. This wood-frame structure is now the Knights of Columbus Hall. The cornerstone for the building was laid on July 4, 1875, and the finished church, capable of seating 250, was blessed in 1877. The cost of the project, including grounds, was $6,135.37. The name, "Star of the Sea", was chosen because the view of the lake seemed to coincide with a venerable church title for Mary, the mother of Jesus.