Фанагория была основана ок. 540 г. до н.э. выходцами из города Теос, находившегося на западном побережье Малой Азии. Не пожелав признать власть Персидской державы, теосцы оставили родину и переселились в Абдеру во Фракии. Рассказ об этом приводит Геродот, но он ничего не говорит об основании Фанагории. Однако краткое упоминание о том, что Фанагория была основана теосцем Фанагором, бежавшим от «персидской дерзости», сохранилось у Арриана (ок. 86–160 гг. н.э.). Стефан Византийский (VI в. н.э.) со ссылкой на писателя рубежа VI–V вв. до н.э. Гекатея сообщает, что Фанагория была названа в честь Фанагора. Псевдо-Скимн (II в. до н.э.) подтверждает, что город основали выходцы из Теоса.
Возможно, что первоначально жители Теоса переселились в Абдеру, но вскоре их часть отправилась оттуда на северные берега Черного моря в район Боспора Киммерийского (Керченского пролива) и основала к востоку от него Фанагорию. Археологические материалы (в первую очередь керамика) подтверждают основание города в 40-х гг. VI в. до н.э.
В греческом мире была распространена практика наименования города по имени легендарного или реального основателя (ойкиста). Однако имена настоящих основателей стали даваться городам в более позднее время, чем когда была основана Фанагория – главным образом, в эпоху эллинизма. Если Фанагор был реальным основателем города, то в случае Фанагории мы должны видеть, возможно, первый пример наименования города в честь ойкиста.
Необходимо упомянуть, что при раскопках Фанагории в ранних слоях был найден фрагмент сосуда, на котором начертано имя Фанагор. Не был ли им основатель города?