Informacje dotyczące Rethymno podczas trwania pierwszego okresu Bizantyjskiego (325-824) oraz podczas okresu panowania arabskiego (824-961) są minimalne. Uwolnienie Krety przez Nikeforosa Fokasa w roku 961 i ponowne włączenie do cesarstwa Bizantyjskiego oznacza początek drugiego okresu Bizantyjskiego który trwał do pojawienia się Wenecjan na wyspie, w roku 1204. Większość domów objętych zostało fortyfikacjami a Castrum Rethemi stanowiło pierwszą postać osady otoczonej fortyfikacjami którą później Wenecjanie nazwali Castel Vecchio. Okres panowania Weneckiego formalnie rozpoczyna się w 1204 roku, gdy przed IV wyprawą krzyżowców, Kreta przeszła pod rozkazy Bonifacego Montferratikos, który później przekazał ją Wenecjanom. W 1206 roku Genueńczyk Enrico (Henryk) Pescatore, notoryczny pirat, zajął wyspę i Wenecja odzyskała ją z powrotem dopiero w 1210 roku. Kreteńczycy reagowali na okupantów serią powstań w okresie 1211-1367. Mimo tych powstań Wenecjanie wprowadzili szereg administracyjnych zmian zgodnie z którymi wyspa została podzielona na sześć sektorów a później w 14 wieku na cztery sektory ze stolicami Chania, Rethymno, Handaka i Sitia. Władzę nad całą wyspą z siedzibą w Handakas sprawował Doukas (Duke) gubernator noszący tytuł księcia. Każdą prowincją Chania, Rethymno i Sitia zarządzał Rektor (Rettore) za pomocą dwóch Radców (Consiglieri).