Едновременно с другите древногръцки градове по нашето Черноморие в периода 580 - 560 г.пр.н.е. възниква и новият град. Основателите му, милетските гърци постепенно и безпроблемно се заселват в тогава съществуващото селище наричано Одесос, като възприемат и името, дадено му от местните жители. За първи път това име се среща при хиоския поет Скимнос и историка Страбон. Градът също е наричан Одисос, а през V век Теофан го споменава под името Одисополис. Приема се, че името има карийски произход и означава "воден град". Подкрепа на това твърдение дава и откритото преди години наколно селище по бреговете на Варненското езеро. Вероятно е създателите на селището да не са нито древните траки, живеещи по земите ни, нито пък гърците, а хора произхождащи от района на Мала Азия и днешна Гърция, и които на много места са оставили имена на селища, завършващи на окончанието "-сос". Съществува и друго мнение, че градът получава името си в чест на Одисей. След VI век в историческите документи името Одесос вече не се среща. Първото споменаване на името Варна е в хрониките за настъпленията на Аспарух и хората му, които "...дошли при т.нар. Варна, близо до Одесос..." и заселването на българите по тези места. От по нататъшните записки на летописците не става съвсем ясно дали това име се отнася за някаква местност в този район, за селище или река. Теофан разказва, че през 774 г. император Константин V се отправил по море на поход срещу българите, но когато дошъл до Варна се уплашил и се върнал. К.Иречек смята, че това име е принадлежало не на стария град Одесос, а на местност в околността, може би Провадийската река и Девненското езеро. Константин Порфироген пише, че Варна е било име на река, същото е и мнението на А.Вретос. От друга страна през 765 г. Никифор съобщава, че капханът на хан Умар бил убит от прислужниците си във Варна. Това убийство не би могло да стане в стария Одесос, тъй като той все още е бил византийско владение. Може би Варна е било някакво селище около Девненското езеро. Според братя Шкорпил тракийско селище с името Варнас е имало по брега на езерото, в района под "Джанавара", където и днес се откриват множество археологични материали. Димитър Димитров пък смята, че Варна е било селище в западната част на днешния град, където има некрополи от времето на халколита. Няма единно мнение за произхода и значението на името "Варна". К.Иречек изказва предположението, че то може да бъде славянско и тъждествено на "врана", вран, черен. За сравнение се посочват сродни славянски думи, произлизащи от старославянската дума uarna, "гарван" - vrana, wrona, ворона. Тогава следва да приемем, че Девненското езеро и Провадийската река са се наричали Черно езеро и Черна река, а името си селището да е получило от тях. Но липсата на славянски поселения в района на езерата до създаването на българската държава дава основание на братя Шкорпил да търсят тракийския корен на името Варнас. Варненският краевед Петър Стоянов посочва интересни находки - в различни части на света, селища с имена като Варна, Варнавино, Варнек и други се намират винаги на брега на река, езеро или море. Той приема, че Варна е било име на близко селище, дало името си на Одесос, и е означавало "град на вода", "воден град". Което всъщност е и превод на името Одесос. В началото на века архимандрит Инокентий дава любопитни подробности от своите изследвания. Той споменава и друго мнение, че името Варна идва от аварската дума вар, означаваща град. Кръстю Мирски пък предполага, че името идва от вар, вар, варовик, имайки предвид, че "в Варна и околността й земята и камъните са варовити..." Те правят податки, че по времето на император Тиберий (14 - 27 г.) за кратко градът се е казвал Тибериополис. В изследванията си археологът П. Георгиев посочва, че съществува надпис от 557 г., според който след смъртта на своята съпруга Теодора император Юстиниан й посветил град, който нарекъл Теодориада, намиращ се на северния бряг на Варненското езеро. Археологът смята, че в продължение на цяло столетие това е първият и първостепенен център на българската държава. При царуването пък на императрица Ирина в края на VIII век също за кратко е носил и нейното име - Иринополис. В древността Теофан наричал града Одесополис, а други автори и Улисополис.