臺東聖教會位於臺東市中山路227巷3號，由陳海水先生創立。

臺東聖教會創立於1961年（民國50年），陳海水本在高雄擔任臺灣水泥公司營業所的主任，由於當時臺泥公司想要在臺東地區開拓營業，便將陳海水調至臺東任職。陳海水於高雄時即參與高雄聖教會，搬遷至臺東後便與教友於自宅家庭聚會，為台東聖教會之始，1963年（民國52年）於臺東市中華路102號購置會堂，1970年（民國59年）搬遷至現址。

由於臺東早期的神職人員較為缺乏，地方性教會也較少，聖教會便邀請高雄、臺南聖教會的牧師前來佈道，並辦理天使托兒所服務社區兒童，走入街道服務鄰里，推廣基督教義。