臺南州菁寮公學校新港東分教場成立於1939年（昭和十四年）間，成立原因主要因學區內就學人口增加，區域內新港東、下長短樹以及竹圍後及新厝之學童需分別徒步前往安溪寮公學校、菁寮公學校及鹽水公學校就讀，學童上、下課十分不便，因此地方人士便爭取於三個街庄之中心點，即今新東國小現址設置「臺南州菁寮公學校新港東分教場」，終止新東村往安溪寮，仕安村往菁寮，竹新村往鹽水國校上、下課之浪費。 根據《臺南州學事一覽》之記載，菁寮公學校新港東分教場成立初期僅有2個學級，共有2個臺灣藉之教員，學生人數共154人。1940年（昭和十五年）學級增加至3學級，教員亦增加為3人，其中1人為日人教師，而學生人數則增加至224人。 戰後，因歷經戰爭，初期之新東國小當時一個年級只有一班，四十幾個學生。根據校友之回憶學校歷經了幾次擴、改建，主要之建設如1953年（民國四十二年）之校長宿舍興建，1955年（民國四十四年）教室及教職員宿舍興建，及1958（年民國四十七年）辦公室之興建。在校舍與辦公室未興建之前，初期之校園基本上仍維持日治時期之規模，校舍為木造，屋頂為和瓦（黑瓦）。校舍之改建自1954年（民國四十三年）開始，至1959年（民國四十八年）之後，原日治時期一層之木造校舍已完全拆除，並改建為一層，且屋頂面為斜面之鋼筋混凝土造校舍。據校友回憶，在木造校舍拆除改建為鋼筋混凝土校舍時期，因學校內之教室不敷使用，亦曾將木造辦公室部份空間規劃為學生教室。此一階段之改建，基本上仍依循日治時期之校園配置，維持前、中、後棟且各棟平行排列。 2009年（民國九十八年）間，新東國小之永續校園計畫，透過新東國小的教師宿舍園區的改造，讓南部地區的大專生能透過實際之操作體驗環境的觀察與改善工作。本次之計畫為以高中生為主體的「八三工作坊」，還有以南部大專生為主體的「古厝新生創意交流活動」。本次活動亦將新東國小校內之舊有宿舍空間，改造成為「八三工室」，成為校園內藝文活動的操作場域。新東國小便在歷任校長之努力下，形成今日面貌。