Фамилия Кандыбов — редкий случай, когда основа, скорее всего, не русская, а тюркская, но оформлена типично русским патронимическим суффиксом -ов. Это значит, что предок носителя фамилии носил прозвище Кандыб, а его потомки стали Кандыбовыми.

Ключ к разгадке — слово «кандыб» или «кандыба». В тюркских языках, особенно в крымскотатарском и ногайском, «кандыба» (или «кандыб») означает «куда ты идешь?», «куда направляешься?». Это не имя в прямом смысле, а типичное для кочевой или полукочевой среды вопросительное прозвище. Такие прозвища давали человеку, который постоянно был в движении, часто отлучался, или, наоборот, рассеянному, вечно ищущему дорогу. В русской ономастике подобные «вопросительные» фамилии встречаются, но редко, и почти все они пришли из тюркской среды (сравните с фамилией Кайдалов, от «кайда» — «куда»).

Суффикс -ов указывает на принадлежность: «чей?» — Кандыбов, то есть сын или потомок Кандыба. Модель образования типична для великорусских фамилий, что говорит о том, что носитель прозвища был крещён и вошёл в русскую социальную структуру, вероятно, в XVI–XVII веках. Встречается фамилия в южнорусских регионах, особенно в бывшей Области Войска Донского и на Кубани, где тюркское влияние на казачество было сильным.

Версия о происхождении от украинского диалектного «кандиба» (неуклюжий, косолапый человек) менее убедительна: слово это редкое, а ударение в фамилии обычно падает на второй слог (Канды́бов), что созвучно тюркскому ударению. Родственных фамилий в русском языке практически нет, что подчёркивает её уникальность. В дореволюционных источниках Кандыбовы встречаются среди казаков и однодворцев.