St. Anastasia Church was organized in 1926 from territory formerly belonging to Immaculate Conception Church. Early masses were said in Holy Child High School. Consturction began in 1926, and the church building was ready in 1927.
A school was opened in 1927 and a rectory built in 1930. In 1954, Our Lady of Humility in Zion was formed, taking some of the northern territory of St. Anastasia Church. In 1963, St. Dismas Church was formed, taking some of St. Anastasia's western territory.
Construction of a new church building began in 1962 and the church was dedicated in 1964. The unique building is a popular local photography subject. The church celebrated its Golden Jubilee in 1976.
When St. Anastasia was formed the majority of parishioners were Irish.