1906년 8월 20일에 사립일신학교로 개교하여, 1919년 3월 21일에 학성공립보통학교 설립인가를 받고, 1919년 5월 20일에 개교하였다. 3·1 병영 만세운동이 본교 운동장에서 시작되었고, 외솔 최현배는 열 네 살 되던 해 봄에 사립일신학교가 창설되자 다른 서당 동무들과 함께 입학하여 3년간 공부하였다. 1947년 9월 1일에 병영국민학교로 교명을 변경하였다.
1986년 12월 1일에 신설 평산국민학교로 14학급이 분리되어 나갔다. 1990년 11월 21일에 도지정 특수교육 시범학교 운영보고회를 가졌다. 1994년 4월 1일에는 신설 삼일국민학교로 27학급이 분리되어 나갔다. 1996년 3월 1일에는 병영초등학교로 교명을 변경하였다. 1996년 8월 4일에 외솔 최현배 선생 얼굴상 제막식을, 1997년 8월 3일에 삼일탑 조형물 제막식을 치렀다.
1998년 10월 30일 울산광역시교육청 지정 특기적성교육 시범학교 운영보고회, 2003년 11월 20일 울산광역시교육청 지정 흡연예방교육시범학교 운영보고회를 가졌다. 2006년 8월 20일에는 개교 100주년 기념식 및 기념비 제막식을, 2007년 2월 25일에는 외솔도서관 개축 준공식을 가졌다. 2007년 3월 1일에 신설 남외초등학교로 2학급이 분리되어 나갔다. 2008년 10월 24일 울산광역시교육청 지정 교육과정(학력향상) 연구학교 운영보고회를 가졌다. 2009년 5월 9일에는 병영초등학교 『일백년사』가 발간되었다.
교훈은 ‘자신을 알고 바르게 생각하며 창의력을 키우는 어린이’이다. 교목은 느티나무이고, 교화는 목련이다. 느티나무의 이미지를 통해 행복, 화합, 평화, 번영, 성장의 가치를, 목련의 이미지를 통해 희망, 꿈, 우아, 청결, 순결의 가치를 실현하는 인재를 양성하고자 한다.
교육목표는 더불어 살아가는 바른 행동을 하는 어린이(도덕인), 기초가 충실하여 스스로 해결하는 어린이(자주인), 창의적인 생각으로 꿈을 키우는 어린이(창조인), 즐겁게 생활하며 몸과 마음이 건강한 어린이(건강인)를 양성하는 데 두고 있다.
최현배를 기리기 위해, 한글사랑 실천운동-최현배 선생님 따라 걷기를 특색사업으로 삼고 있다. 학생들에게 우리의 말과 글에 대한 애정과 자부심을 갖도록 하고, 한글 사랑의 마음을 생활 속에서 실천할 수 있도록 하고 있다. 교육복지 투자우선지역사업의 일환으로 ‘느티나무 그늘 아래’, ‘실력이 쑥쑥’, ‘행복가득 도움반’, ‘네 꿈을 펼쳐라’, ‘아름다운 동행’, ‘산타 365’, ‘무지개 교실’, ‘늘 푸른 교실’, ‘어깨동무’, ‘교육복지실’ 운영 등을 구체적으로 전개하고 있다.
2010년 3월 1일 현재 28학급(특수학급 2학급 포함)에 학생 764명, 교직원 40명이다. 2010년 2월 18일 제91회 졸업식을 하였고, 총 18,562명의 졸업생을 배출하였다.