Naval Base Secondary School was established in 1957, when the British set aside land in the Naval Base at the former Bah Tan Road to build a school. It was the first full school in the English medium in Singapore, with students from Primary One to Secondary Four. In those days, it was the only secondary school in Sembawang.
As the school was located within the Naval Base, security was tight. Teachers and workers had all ten fingers printed and photographs taken before they were issued entry passes. Students had to enter through the Canberra Gate, where police were on guard duty.
Due to development in Sembawang and the need for better facilities, the school finally moved to its current building in Yishun in 1988.