Атлант мұхитының алабына еніп, Кіші Азия мен Еуропа құрлығын байланыстырып жатқан бұл теңіз "Қара теңіз" атауын бірден алмаған. Тарихи еңбектер мен деректерде қара теңіздің 300-ден аса көне атауы кездеседі екен. Жағасында өмір сүрген тайпалар атауымен Сарматтық, Скифтік, Киимерлік, Спермдік, Фракийлік, Римдік теңіз деп аталған кездері де болған.

Арабтар Солтүстік теңіз деп атаса, гректер мен римдіктер – Шығыстық теңіз деген ат берген. Ал алғашқы грекиялық жаулап алушылар бұл теңізді жиі соғатын дауылды ауа-райы үшін және жағасында тұратын жауынгер халық үшін Понт Аксинский деп те атаған.

Кейіннен, теңіз жағасынан көптеген қалалар салып, әбден орнығып алған соң теңіздің атауын Понт Эвкинский, яғни "Қонақжай теңіз" деп өзгерткен. Ежелгі парсы деректерінде, Қара теңіз атауы – "ахшайна" деген атаумен кездеседі. "Ахшайна" парсы тілінде қара-көк немесе қараңғы деген мағынаны білдіреді.

Қара теңізбен ежелгі түрік тайпалары 13-14 ғасырлардағы соғыс жорықтары кезінде танысқан. Жерорта теңізін "Ак дениз" деп атайтын түріктер, Қара теңізді "Кара Дениз" деп атаған.

Ал теңіздің қазіргі аталуында теңіздің өзіндік табиғи ерекшеліктері мен теңіздің қара түсі негізге алынған. Теңіз суында күкіртті сутектің мөлшері шамадан тыс көп болғандықтан суға тасталған зәкір немесе тағы басқа заттар қарайып кететін болған. Сондықтан теңізшілер теңіз тұңғиығы қап-қара түсті деп есептеген. Осылайша, онсыз да қара теңіз ресми түрде "Қара теңіз" деген атау алған.