Saint Mark Lutheran Church began in February 1951 with Sunday school classes held in the home of Mr.& Mrs. Wayland Campbell, members of Our Redeemer Lutheran Church in Honolulu. Results of canvassing done that fall were encouraging enough to persuade the Board of Missions to assign a vicar to the field.
The first service of the Puohala Mission was held at Castle High School in 1952. Puohala Missions was organized as Saint Mark Lutheran Church in 1954 with Rev. Norman J. Bangert installed as the first pastor. Later that year, a church site was purchased and an architect retained to draw up plans for the first increment and the parsonage. The pastor moved into the parsonage in 1955 and the parish hall chapel was dedicated in September of that year.
Rapid growth of the Sunday school and a desire to start a Christian Day School moved the congregation to build a small classroom adjoining the chapel. In 1956, Saint Mark Lutheran School opened its doors for the first time to 12 kindergarteners. A year later the school expanded to include the first three grades and Miss Mary Helen Hahn was called to be the first Principal of Saint Mark Lutheran School.
By September of 1959 school offices and a second large classroom were dedicated and the enrollment grew to 70 pupils. In 1962 and again in 1966, additional property was purchased to help accommodate the increased enrollment. In 1969, the school had grown to include both 7th and 8th grade.
In May of 1970, Saint Mark Lutheran School held its first 8th grade graduation, graduating nine students. The school campus grew in 2002 to include a gymnasium, band room, and four additional classrooms that currently house the junior high.