Фамилия Колтаков — типичный пример русского «прозвищного» образования: её основа — личное прозвище Колтак, а суффикс -ов указывает на принадлежность («чей?» — сын Колтака). Такая модель была одной из самых распространённых в XVI–XVII веках, когда фамилии закреплялись за крестьянами и посадскими людьми.

Прозвище Колтак, скорее всего, связано с диалектным глаголом «колтыхать». У этого слова два основных значения: «ходить вперевалку, ковылять» и «много говорить, болтать». Первое могло указывать на заметную хромоту или раскачивающуюся походку, второе — на говорливость и привычку пустословить. В народе такие прозвища давали метко и без злого умысла, просто как бытовую примету.

Есть и другая, менее очевидная версия — связь с тюркским словом qoituq, что значит «лесть». Она допустима, но слабее: во-первых, фамилия не характерна для регионов с сильным тюркским влиянием (она встречается в основном в центральной России и на Урале), во-вторых, глагольная основа «колтыхать» объясняет прозвище проще и без привлечения заимствований. Поэтому славянская версия выглядит правдоподобнее.

Самый известный носитель фамилии — Сергей Михайлович Колтаков (родился в 1955 году в Барнауле), советский и российский актёр. Его происхождение косвенно подтверждает, что фамилия была распространена на Алтае и в Сибири — регионах, куда в XIX веке активно переселялись крестьяне из европейской части России.