Фамилия Нартоков напрямую связана с миром героического эпоса. Её основа — имя Нарт, которое носили легендарные богатыри в сказаниях многих народов Кавказа. Нартский эпос бытует у адыгов (кабардинцев, черкесов и адыгейцев), абазин, осетин, а также известен абхазам, чеченцам, ингушам, карачаевцам и балкарцам. Основу эпоса составляют сказания о происхождении и приключениях героев-богатырей — «нартов».

Самый простой и правдоподобный путь образования фамилии — от личного имени Нарток, которое, в свою очередь, восходит к имени эпического героя Нарта. Суффикс -ок в адыгских именах часто выполнял роль ласкательного или уменьшительного, поэтому Нарток можно перевести как «маленький Нарт» или «Нартёнок». Имя было вполне реальным: у адыгов встречаются имена, образованные от бытовых понятий, например, Калашау («городской парень»), Хагур («худой, тощий»), Учужук («сын ставшего на ноги») или Гучешау («сын кузнеца»). Так что наречение ребёнка в честь эпического героя — обычная практика, а фамилия Нартоков буквально означает «потомок Нарта».

Слово «нарт» — тёмное и спорное. Единого мнения о его происхождении нет, и это добавляет фамилии глубины. По одной из версий, оно восходит к иранскому «nar» — «мужчина». Другие исследователи сближают его с осетинским «нае арт» — «наш огонь». Есть и более экзотические гипотезы: от древнеиндийского корня «нрт» («плясать») или от монгольского «нара» — «солнце». Сторонники последней версии напоминают, что многие герои эпоса связаны с солярным мифом, а «нарт» могло образоваться добавлением суффикса «-т», который в осетинском языке указывает на множественное число. Какая из версий верна — вопрос открытый, но для носителя фамилии важно другое: её обладатель носит имя, которое веками звучало в сказаниях о силе, чести и подвигах.

Русская фамилия Нартоков оформлена стандартным патронимическим суффиксом -ов, который добавлялся к адыгским именам при документальном оформлении в Российской империи. Так что перед нами типичный пример адаптации кавказского имени в русскую фамильную модель. Встречается она преимущественно у кабардинцев и черкесов, а также у других народов, воспринявших адыгскую культуру.