NCC har sina rötter i det 1890 grundade rederiaktiebolaget Nordstjernan AB, som 1961 skapade ett eget byggbolag med namnet Johnson Construction Company (JCC). Bolaget i sin nuvarande form bildades 1988 genom en sammanslagning av JCC och dåvarande ABV (Armerad Betong Vägförbättringar). Det nya företaget fick namnet NCC, med Nordstjernan som ägare.