Az elnevezés az ógörög Erüthra Thalassza (Ερυθρὰ Θάλασσα) névből származik, amelynek Vörös-tenger a fordítása. A híres ókori görög történetíró, a Kr. e. V. században élt és alkotott Halikarnasszoszi Hérodotosz a tenger déli területére használta ezt az elnevezést.
Ezért néhány ókori klasszika filológus interpretációja szerint - abból kiindulva, hogy
az antik ázsiai nyelvekben szokás volt színekkel is jelölni az egyes égtájakat,
így a déli vidékek megjelölésére a vörös szót használták - a tenger elnevezése elsősorban a fekvésére, a forró sivatagokkal övezett környezetére utal.
A rómaiak a görög elnevezéssel azonosan ugyancsak a Mare Rubrum (latinból: Vörös-tenger) elnevezéssel illették az Indiai-óceán melléktengerét. A VII. századi arab hódítások idejétől, az arab népek is Vörös-tengerként (Al-Baḥar Al-Aḥmar, البحر الأحمر) jelölték a kék számtalan színárnyalatában játszó víztömeget.
Akadtak azonban ettől eltérő elnevezések is;
a kora középkori geográfusok közül egyesek Mare Mecca (Mekkai-tenger) vagy Sinus Arabicus (Arab-öböl) néven jelölték meg a térképeiken.
A tenger mentén élő arab népek hagyományában
a vörös szín a víztömeg partvidékét határoló kopár hegyekről kapta a nevét;
napnyugtakor az alacsonyan beeső napsugarak fényében vöröses-okkerszínekben játszanak a kopár sziklák, és ezek színét tükrözi vissza a víz.
Nagyon ritkán, de előfordul, hogy a pávatollakat is megszégyenítő smaragd-türkiz színekben játszó, és a Vörös-tenger partjait jellemző szegélyzátonyok feletti (a korallzátonyok egy típusa, a szerk.) sekély víz zavaros vörösbarnára vált.
Ilyenkor az amúgy kristálytiszta és átlátszó víz helyenként olyanná válik,
mintha egy hatalmas szippantókocsi tartalmát zúdították volna a vízbe.
Még mielőtt bárki valamilyen környezet ellen elkövetett merényletre gondolna, sietve le kell hogy szögezzük, ennek a rendkívül ritka jelenségnek biológiai magyarázata van.
A part menti vizek vörösre válását ugyanis egy baktériumtörzs, a korábban tévesen kékmoszatnak nevezett fonalas cianobaktériumok egy fajának, a Trichodesmium erythraeum egyedeinek robbanásszerű, ideiglenes túlszaporodása okozza.
Ez a fajta „algavirágzás” csak a Vörös-tenger, illetve az ausztráliai Nagy-korallzátony, valamint a nyugat-pacifikus melanéziai szigetek környékén fordul elő.
Amikor akár az egyiptomi, akár a szaúd-arábiai partszakaszon rövid időre felszaporodnak a fonalas cianobaktériumok, a part menti vizek valóban vörössé válnak, mintegy a „legkékebb tenger”elnevezésének alátámasztására.