The first Catholic to visit Tennesse was actually Hernando De Soto who led the first European expedition into North America. In June of 1540, he and his party camped near Chattanooga and Holy Mass was celebrated at the encampment. 
The first diocese in the United States was established in Baltimore in 1789 and it included every one of the thirteen states.         
In 1808 Benedict Joseph Flaget became the first Bishop of the newly established diocese of Bardstown, Kentucky which included all of the State of Tennessee.
Thirty years later on September 16, 1838 Bishop Rosati of St. Louis constituted  Richard Pius Miles Bishop of Nashville at the  Cathedral of Bardstown .
His diocese which he covered on horseback encompassed 42,000 square miles.
The first priest to serve East Tennessee was William Howard, a native of County Cork, Ireland who was ordained by Bishop Miles in 1843 and given the mission to minister to 70 eastern Tennessee counties, an area roughly the size of New York State.
More than 20 years passed before there was a church in Greeneville. On August 31, 1869 Felix Reeve, a non-Catholic,  granted a half acre on High Street later Called College Street to P.A. Feehan who had been appointed Bishop of Nashville in 1865.
Bishop Feehan had been born in Ireland and ordained in St. Louis in 1852. The following year when a cholera epidemic he was heroic in serving the sick and dying. In 1858 he established the St. Vincent de Paul Society to aid the poor. He is remembered for his service to the wounded soldiers after the Battle of Shiloh.
By 1870 Greeneville finally had a church. St. Patrick’s Church was dedicated by Bishop Feehan on October 16, 1870. Tradition says that President Andrew Johnson donated $500 to the building fund was in attendance.
The railroad granted half-fare rates so that those from as far away as Morristown could attend.
While Irish-born Father Francis Marron was the first priest to serve St. Patrick Church, it was Tennessee-born Father Emmanuel Callahan who rode his horse Rebel to minister to 34 of the 36 counties of the Diocese of Knoxville.
Twice in the 20th Century St. Patrick Church was renovated, but by 1950 the decision was made to sell the property and demolish the church building.
Between 1950 and 1955 the Catholics of Greeneville celebrated Holy Mass in the Capitol Theatre.
By 1954 the parish had saved enough to buy almost 7 acres on Mt. Bethel Rd and on April 25,  1955 Notre Dame was dedicated with William Adrian, Bishop of Tennessee as officiant.