勝利國民小學的前身為竹園公學校，創設於1939年（昭和十四年），為臺南市日治後期所設立的學校，專供臺籍學童就讀。1941年（昭和十六年），易名為「臺南市竹園國民學校」。 二戰後，國民政府來臺，因學校為當時臺南市東區唯一的小學，於1946年（民國三十五年）改稱為「臺南市東區國民學校」，同年，校門前的道路「竹園町」，因慶祝國民政府八年對日抗戰勝利，改名為「勝利路」。學校亦於1947年（民國三十六年），更名為「臺南市東區勝利國民學校」。 1968年（民國五十七年），政府實施九年國民教育後，再度更名為「臺南市東區勝利國民小學」，即為現今之校名。勝利國小原有禮堂一座，在1952年（民國四十一年）11月於貝斯颱風侵臺時，禮堂被火所燒毀，遂於1953年（民國四十二年）時在原處重建禮堂，並於同年9月25日完工。