Neolityczne muszle, które zostały znalezione w czasie badań wykopaliskowych przeprowadzonych na kamienistym pagórku w miejscowości Paleokastro, zdradzają istnienie życia w tamtym okresie. Nie ma też wątpliwości co do istnienia osady w okresie pominojskim(1350-1250 p.n.e.), co udowodnione zostało odkryciem w regionie Mastambas (Rethymno) wykutego grobu. Najbogatsze wiadomości o starożytnym mieście Rithymna, pochodzą z opisów monet z 4-ego i 3-ego wieku p.n.e. mających z jednej strony wizerunek głowy Apollona lub Ateny a na rewersie uwidocznione morskie oznaczenia: dwa delfiny lub trójząb Również pisarze z 2-ego, 3-ego i 4-ego wieku podają wartościowe informacje o Rithymnie. Plinios (1 w naszej erze) i Klaudious Ptolemeous (2-gi w naszej erze) umiejscawiają miejscowość pomiędzy miejscowościami Panormo i Georgiupolis ,natomiast Klaudiusz Ailianos (3 w naszej erze)jako pierwszy opisuje istnienie świątyni Rokkeas Artemis. Rzeźbienie, które zaobserwowano na naturalnym głazie na wzniesieniu Palaiokastro stanowią dowód istnienia świątyni na tym wzniesieniu. W dodatku nazwa „Paleokastro”(stary zamek) stosowana nawet przez Wenecjan, zdradza, że kiedyś tam była fortyfikacja z przeszłości.

Nie można dokładnie określić położenia osady starożytnej Rethymni, jednak kilka opisów weneckich oraz archeologicznych znalezisk z okolic ulicy Arkadiou i Urzędu celnego prowadzą do wniosków, że w miejscu dzisiejszego miasta Rethymno istniała osada. Bardzo prawdopodobne jest również to, że miasto przejęło nazwę starożytnej Rethymni, która przez to pozostała żywa aż do naszych czasów.