Þann 21. júlí 1997 var fyrsta skóflustunga tekin að Heiðarskóla. Heiðarskóli er byggður sem tveggja hliðstæðna heildstæður grunnskóli, sem er tvær bekkjardeildir í árgangi frá 1. – 10. bekk. Hann er jafnframt fyrsti skólinn á Íslandi, sem byggður er í einum áfanga, með íþróttahúsi og sundlaug. Skólinn tók síðan til starfa haustið 1999.
Í stuttu máli er skólinn þannig byggður að eftir honum endilöngum er breiður og bjartur gangur, stundum kallaður „menntavegurinn”. Sunnan megin við ganginn eru verk- og tónmenntastofur, auk raungreinastofa. Norðan megin við ganginn eru þrjú kennslustofuhús á tveimur hæðum, alls 6 almennar kennslustofur í hverju húsi. Kennslustofuhúsin eru auðkennd með litum, gult (yngsta stig), rautt (miðstig) og blátt (unglingastig). Hægt er að opna á milli tveggja stofa á hverri hæð. Í miðrými skólans er samkomusalur/matsalur á neðri hæð, en stjórnun, bókasafn, tölvuver og aðstaða hjúkrunarfræðings á efri hæðinni. Út frá miðrýminu í norðurátt er aðstaða til íþróttaiðkunar, sundlaug og íþróttasalur. Við skólann hafa einnig verið settar þrjár lausar kennslustofur (svo kallaðir kálfar), sem eru notaðar undir almenna kennslu, forskóla tónmenntar og Frístundaskólann.
Stjórnun Heiðarskóla hefur verið með eftirfarandi hætti:
Ár Skólastjóri Aðstoðarskólastjóri
1999-2001 Árný Inga Pálsdóttir Gunnar Þór Jónsson
2001-2003 Gunnar Þór Jónsson Björn Víkingur Skúlason
2003- Gunnar Þór Jónsson Sóley Halla Þórhallsdóttir