​In 1953 St. Anastasia Church was established in honor of James Francis Cardinal McIntyre’s elevation to the Sacred College of Cardinals. That fall, St. Anastasia School opened with a single first grade class at neighboring St. Mark’s parish in Venice.

By 1955, construction began on an eight-room school building, and grades one through four were opened in the fall of that year with two Sisters of the Holy Names of Jesus and Mary and two lay teachers, staffing the school. Throughout the 1950s, St. Anastasia grew rapidly adding a new class yearly; and in 1961, the original first class of fifty-three students graduated in June.​

Enrollment peaked in 1964 with 771 students in two classes per grade, one to eight.

As the school grew, so did the city of Los Angeles. The Los Angeles International Airport began an expansion initiative which caused a corresponding reduction in the size of St. Anastasia parish as well as its school. As the classroom size shrunk, new developments grew. St. Anastasia now had space to create a science room, staff lounge, audio-visual room, and a parish community room.

The 1980’s brought many new transitions beginning in 1981 when the Sisters of the Holy Names of Jesus and Mary withdrew from the school, opening it to a lay administrator for the first time before a Sister of St. Joseph of Carondelet assumed administrative duties in 1982. Donations from outside foundations also helped St. Anastasia grow and expand. The Fritz B. Burns Foundation helped the school create a new library in 1983 and open a Kindergarten in 1984. Their continued support in 1986 and 1988 allowed the school to open a new science center and a computer lab.

Throughout the years both the Fritz B. Burns Foundation and the William H. Hannon Foundation have continued to actively support St. Anastasia through generous monetary grants.

In 1988 the school came under the direction of a lay administrator.

In an effort to update and expand the school’s curriculum, St. Anastasia added computer and Spanish classes to all grades in the 1990’s. In addition, the Catholic Youth Organization sports program was expanded to include third through fifth grade students. In 1994 an art enrichment program, Gateway to Art, was added to the curriculum.

In 2000 the first spring musical was performed under the direction of the music program. Through the subsequent years the production of the musical shifted to parents and community members. The In 2002, the Monsignor Royale M. Vadakin Arts and Education Fund was established in the parish. Its purpose is to enhance the arts and spiritual education in the parish and school. Through this fund, the school has been fortunate to expand its enrichment programs including the Talent Show, Performing Arts Showcase, musicals, retreats, and public speakers.

In 2009, all staff put grades on-line in Gradelink for quick and current communication with parents. In 2011 the school embarked on a one to one digital device program in order to integrate technology and learning.

In 2010, the school name was changed to St. Anastasia Catholic School to emphasize the school’s Catholic faith identity.

In August 2013, the school opened the first junior kindergarten with twenty-two students, the Class of 2023. In August 2021, the school opened a second junior kindergarten class.