Stallings was ordained a priest in 1974. His first assignment was as an associate pastor at Our Lady of Peace Church, Washington, D.C. In 1976, at the age of 28 years and just two years after ordination as a priest, he was named a pastor of St. Teresa of Avila parish in Washington. He was the pastor of this church for 14 years. During Stallings' pastorate, the parish become known for its integration of African-American culture and gospel music in the Mass.