Mit o egipatskom porijeklu romskog naroda potiče iz 15. stoljeća. Smatralo se da je ova skupina porijeklom iz Malog Egipta, što je pojam koji je u srednjem vijeku označavao današnje područje Kipra i Sirije. Stoga su pridošlice nazvani otprilike "Egzipci".

Danas se smatra da je njegovo porijeklo iz sjeverozapadne Indije, tačnije iz Pendžaba, iako neki autori sugeriraju da su iz današnje indijske države Uttar Pradesha. Glavne naznake ovog porijekla nalaze se u romskom jeziku, izvornom jeziku, čiji rječnik ima mnogo sličnosti sa sanskrtom.

Historija Roma do njihovog dolaska u Evropu ima mnogo praznina. Iseljavanje iz Indije, vjerojatno je započelo u jedanaestom stoljeću, imalo je nekoliko faza i slijedilo je različite rute. Perzija, Armenija i Grčka bile su tri faze, na što ukazuje činjenica da Romi imaju brojne izraze perzijskog, armenskog i grčkog porijekla.

Romska etnička skupina iskristalizirala se tokom raseljavanja, posebno u Evropi i naročito na Balkanu, koji je od početka prihvatio grupe Roma i kojeg se može smatrati njihovom pravom kolijevkom.

Krajem 14. stoljeća, širenje Osmanskog carstva u istočnoj Evropi potaklo je Rome na posljednju faze migracije i prodor u zapadnu Evropu. Za njih je to bilo poput hodočašća, istovremeno održavanje svoje islamske prošlosti i putovanje u sveta mjesta kršćanstva kao što su Rim ili Santiago de Compostela.

Njihova prisutnost u zapadnoj Evropi bilježi se od prvih godina 15. stoljeća. U zemljama Svetog Rimskog Carstva jedan se ljetopisac osvrnuo na dolazak između 300 i 500 porodica u Lübeck 1417. godine. Druga hronika bilježi ulazak u Švicarsku sljedeće godine 14.000 Roma podijeljenih u različite skupine. Godine 1424. razne grupe do 300 Roma, “s mnogo žena i djece”, stigle su u Regensburg na Rajni. U Flandriju su stigli 1422, a u Pariz 1427. godine.

Putnici, predvođeni muškarcima s plemićkim titulama poput grofova ili vojvoda, koristili su prednosti religioznog okruženja tog vremena kako bi primijenili svoju strategiju i tako povećali svoje izglede za opstanak. Tako francuska hronika objašnjava da je 1427. godine “u Pariz stiglo dvanaest pokajnika, naime vojvoda, grof i deset ljudi, svi na konjima, koji su se nazivali dobrim kršćanima, iz Donjeg Egipta”.

Rekli su da su ih u prošlosti muslimani napadali i prisiljavali da promijene vjeru, ali da su ih kasnije car i drugi kršćanski pokorili i ne samo da su ih prisilili da se vrate u kršćanstvo, već ih i osudili na to. Iako im je izgled bio neobičan, uvjeravali su da su plemeniti. "Gotovo svima su bile probušena oba uha i svaki je nosio jednu ili dvije srebrne naušnice, rekli su da je to u njihovoj zemlji znak plemenitosti."

Tvrdili su da sa sobom nose dokumente u kojima stoji da im različiti suvereni garantiraju sigurnost. Naprimjer, takozvani vojvoda Mihael od Egipta i njegovi sljedbenici izložili su 1422. godine u Baselu pismo od pape, međutim, nema nikakvih podataka o vjerodostojnosti ovih dokumenata.

U nekim su prilikama Romi izazivali neugodnosti pa čak i neprijateljske reakcije. Hronika piše o onima koji su stigli u Tournai, u Belgiji. “Većina ih je zarađivala za život krađom, posebno žene koje su bile jako loše odjevene i ulazile u kuće, neke su prosile [...] i bilo je teško biti na oprezu i ne ostati bez nečega od imovine.”

Na Iberijski poluotok došli su u drugoj polovini 15. stoljeća iz Grčke, zbog čega su ih nazivali Grcima, iako je naziv Roma uglavnom bio prihvaćen. U oba vala migranata bilo je riječ o grupama ljudi koji su se predstavljali kao politički ili vjerski emigranti, pokajnici i hodočasnici, pa ih stanovnici poluotoka nisu gledali negativno,.

Otkako su se naselili u Evropi, Romi su dobili vrlo različita imena. Cigani vjerojatno potječe od tchinganes, "čovjeka različitih rasa" na sanskrtu, kako su sami sebe zvali Cigani. U Francuskoj su ih nazivali manouches ("muškarci"), što je naziv koji također dolazi iz sanskrta. Zvali su ih i boemima zbog prolaska tim srednjevropskim teritorijem ili Saracenima, jer su dolazili iz zemalja u kojima je dominirao islam.