早在1580年代，英国人曾经两次航行到现在北卡的罗阿诺克岛（Roanoke Island）建立殖民点，但是都没有保持下来。第二次是在1587年，登陆的人当中有一对夫妇，他们的女儿弗吉尼亚•戴尔（Virginia Dare）在那里出生，是北美土地上英国人的第一个婴儿。三年后她的外祖父从英国取得补给品返回，殖民点已经人去室空，仅仅在一棵树干上发现了“CROATOAN”字样，迄今无人破解，因此罗阿诺克殖民点被人们称为“失落的殖民地”（The Lost Colony），是北美殖民史上最古老的谜团之一。
一直到1655年，才终于有人从弗吉尼亚南下到这块土地上定居。再后来，1663年英王给8个英国贵族颁发了建立卡罗来纳的特许状。与其它英国的北美殖民地不同，卡罗来纳是所谓的专有权殖民地（proprietary colony），受颁的个人或团体享有全权自治。但是这8个家族在防务、施政以及农地分配制度上的观点各不相同，以致后来分成了南北两个卡罗来纳，并且在1729年都成为皇家殖民地（royal colony）。
因为殖民者最早来到的是卡罗来纳北部地区，所以北卡罗来纳州就被称为“老北方州”（The Old North State），现在该州的州歌也以此为名。要注意的是，不要把它和南北战争时期的北方州混淆起来，北卡州在那个时候是分离主义的南方邦联成员之一。
北卡罗来纳最有名的昵称是“焦油脚跟州”（Tar Heel State）。早年北卡有大面积的长针叶松树，从松树的树干上可以取得松节油，方法类似于橡胶树割胶，此外烘烤松木还可以产生木焦油，用它们涂抹船只的木头船壳可以防腐防漏，因此造船、运输和渔业都离不开它。美国独立战争之前，北卡每年出口的木焦油和松脂超过10万桶，比任何其他殖民地都多。
炼制木焦油是个脏活，工人要把松木堆起来，盖上泥土点火焖烧，焦油就会从木堆下面挖的沟里流出来。它常常会漫溢到沟外，沾上工人的鞋底，焦油脚跟州的绰号就不胫而走。
这个昵称的来源还有另外好几个说法。其中之一说的是在独立战争的时候，1781年5月康沃利斯勋爵（Lord Cornwallis）率领驻守北卡的英军渡过焦油河（Tar River）前往弗吉尼亚的约克敦，被爱国者倾倒在河里的木焦油粘在脚底，阻滞了英军的行动。因为这一说法到20世纪才见诸记录，所以被许多人认为是一个杜撰出来的故事，用来解释为什么那条河名叫焦油河。
焦油脚跟州被该州多数人接受的说法源自南北战争时期。在一次激战中，友军被联邦军队击溃，当弗吉尼亚的军人撤退，路过北卡军团坚守的阵地时，以嘲笑的口吻问：伙计们，老北方州脚底下还沾有焦油吗？北卡军人立即回应：一点都没啦，都让老杰夫（old Jeff，指邦联总统杰斐逊•戴维斯）买走啦。对方问：为啥？他拿去做什么？北卡军人说：他准备用来沾在你们的脚后跟，下回打仗的时候你们就会坚持得好一点。
南方军队的总司令罗伯特•李将军（Robert Lee）听到了这个故事，感叹地说：上帝保佑焦油脚跟孩子们（God bless the Tar Hell boys）。无论这件事的真实性如何，北卡州人都以焦油脚跟为骄傲，就连美国大学体育联盟劲旅、北卡州立大学教堂山分校的代表队也用Tar Heel为自己命名。
北卡州还有一些广为人知的其他绰号，其中最著名的就是“飞行第一州”（First in Flight State），因为莱特兄弟于1903年在北卡州海边的小鹰镇（Kitty Hawk）沙滩上，成功地进行了世界上第一架有人操纵的、重于空气的固定翼动力飞机飞行。现在那里有莱特兄弟国家纪念馆，而且北卡州非商业车辆的默认车牌上也印有First in Flight字样。
