Z Indie Romové odcházejí někdy mezi 5. a 10. stoletím. A to nejprve do Persie, kde zřejmě po určitou dobu setrvávají, o čemž svědčí perská slova, která se objevují v jednotlivých dialektech romštiny. O příchodu skupiny indických hudebníků do Persie referuje mimo jiné básník Firdausí ve své Knize šáhů (r. 1011). Tento básník klade do doby panování Bahrama Ghura (420-438) jeho žádost indickému králi Šankalatovi o vyslání hudebníků do Persie: "Když to Šankalat provedl, Bahram je rozsídlil po svém království, nařídil lidem, aby je zaměstnali... A z jejich potomků pocházejí tmaví Luriové, kteří jsou mistry v hraní na flétnu a loutnu." Z dochovaných dokumentů však nelze jednoznačně určit, zda se jednalo o Romy.

Po odchodu z Persie se zřejmě Romové v 8. století rozdělili jižně od Kaspického moře do skupin a putovali jednak do Arménie, jednak do Sýrie a Palestiny. Na Balkáně (Byzantská říše) se snad první Romové objevují v 9.-11. století. V Byzantské říši dostávají také své pojmenování, pod kterým jsou známi později v Evropě. Gruzínský mnich nazval v roce 1054 skupinu lidí, která zbavila okolí Konstantinopole jedovatých hadů, řeckým slovem Athinganoi (z tohoto slova jsou odvozována jména Cikán, Zigeuner, Cygan atp.). Toto pojmenování mělo od počátku hanlivý nádech, bylo totiž původně označením heretické sekty.

O usazování Romů v Byzantské říši již existují spolehlivější zprávy. Ve zprávách tehdejších poutníků jsou zachovány např. informace o romském osídlení řeckého přístavu Modon. V první z těchto zpráv jsou zmíněni v roce 1384 Romiti. V Modonu postupně počet Romů klesal, ve 14. století měla jejich osada 300 domů, ale v 16. století zbylo pouhých 30 domů. Příčinou byly zřejmě turecké výboje, které začaly přímo ohrožovat Byzantskou říši, a s tím související úpadek obchodu. Romové se v tomto období živili kovářstvím, kotlářstvím a dalšími řemesly a také provozováním akrobacie a různých triků.

Od první čtvrtiny 15. století se podle dochovaných zpráv začínají Romové objevovat ve střední a západní Evropě. Při svém putování jsou v mnohých případech vybaveni ochrannými glejty vladařů, které jim zaručují bezpečnost. Jedna z těchto listin vydaná císařem Zikmundem na Spišském hradě zaručovala vojvodovi Ladislavovi a jeho lidem svobodný průchod zemí a dávala mu právo na souzení sporů uvnitř komunity. Jiná listina vydaná ve Španělsku v roce 1425 zaručovala volný pohyb skupině hraběte Michala, který byl osvobozen od placení cel a poplatků.

Romové přicházejí do střední a západní Evropy ve skupinách čítajících od několika desítek mužů, žen a dětí až po stovky členů. Přicházejí pod vedením jednotlivých vůdců, kteří jsou titulováni jako hrabata resp. vojvodové. Jak vypadal vstup takové skupiny do města, se dozvídáme ze záznamu z roku 1427 z Paříže. Nejprve přišel vůdce skupiny společně s deseti jezdci. O den později se objevila skupina čítající více než 100 osob. V dobových záznamech jsou Romové v některých případech označováni jako Saracéni nebo pohané resp. Cikáni.

Včeských zemích se první nesporná zmínka o Romech datuje roku 1417 ("toho léta se po zemi české Cikáni vláčili a lidi mámili"). O rok později prošla zřejmě na českém území další skupina, jak o tom svědčí záznamy ze Znojma a z Chebu. Od 20. let 15. století se v regionu střední a západní Evropy pohybují poměrně často skupiny Romů, kteří na základě ochranných glejtů a tvrzení, že byli vyhnáni ze své země Turky, dostávají v jednotlivých městech almužnu.