V priebehu celej histórie sa nám o Cigánoch a kočovníkoch zachovali iba dokumenty, ktoré napísali príslušníci iných národov. Samotní Cigáni nezanechali o sebe nijaké dobré, alebo zlé, skutočné, či vymyslené písomné zmienky. V kolektívnej pamäti sa uchovali viac legendy ako faktami podložené udalosti. Prvé cigánske skupiny prichádzali do Európy z východu v 14. a 15. storočí. Európa ich prijala s prekvapením, obavou a nepochopením. Obyvatelia dedín a miest dávali týmto dlhovlasým tulákom na koňoch rôzne mená zodpovedajúce dohadom o ich pôvode a zle pochopenej etnickej príslušnosti. Boli to ľudia, ktorých nebolo možné zaradiť do nijakej spoločenskej vrstvy. V týchto podmienkach, aj keby moderní historici boli čerpali z archívov, ktoré nemajú, sa nedá s istotou povedať, že uvedené obdobie potvrdzuje prítomnosť prvých cigánskych skupín. Je možné, že tieto malé skupiny nepozorovane prechádzali cez regióny, nezanechajúc za sebou nijaké stopy v archívnych materiáloch: to dokazuje, že prvé svedectvo v danej krajine môže hovoriť o historicky nezachytenom pohybe na území bez hraníc. Situácia je o to zložitejšia, že bádatelia mohli za Cigánov pokladať necigánske skupiny a vyvolať domnienku predchádzajúcej prítomnosti cigánskeho spoločenstva, čo historicky potvrdili. V Grécku je napríklad niekoľko storočí známa heretická sekta nazývaná Atsinganos alebo Atsinkanos (nedotknutí, nedotknuteľní) a istý mních z hory Athos spomína okolo roku 1100 prítomnosť skupiny Atsingani.

Jej členovia prišli z Malej Ázie a boli známi ako dobrí kúzelníci a veštci. Zdá sa, že podľa sekty boli vo viacerých krajinách nazvané všetky skupiny kočovníkov prichádzajúce z východu: Tsiganes vo Francúzsku, Zigeuner v Nemecku, Sigöyner v Nórsku, Zingari v Taliansku, Ciganos v Portugalsku atď. V Byzantskej ríši bol však taký pohyb rôznorodého obyvateľstva, že nie je isté, či nositeľmi pomenovania Atsingani neboli odlišné skupiny. Je tiež možné, že tí, ktorí sa po opustení Grécka stali príslušníkmi skupiny Cigánov, boli naozaj v roku 1100 v Grécku. Istý Albertinus Cingarellus spomína v roku 1262 v Ligúrii prítomnosť skupiny Tigani, o ktorej je zmienka i v gréckych listinách južného Talianska v 12. a 13. storočí. Tigani boli bezpochyby kováči. Ani tento doklad však nepotvrdzuje prítomnosť Cigánov. Takýchto príkladov by sme mohli uviesť veľa, prejdime však k historicky overeným údajom. Je pravda, že Cigáni prichádzajú z východu. Až koncom 18. storočia prišli jazykovedci na to, že cigánska reč je bezpochyby jazykom severozápadnej Indie, ktorý je odvedený z nárečí blízkych sanskritu. Podľa rozboru slovnej zásoby a gramatických štruktúr cigánskych dialektov rôznych krajín nám jazykoveda umožňuje vytvoriť si predstavu o pohybe národa, potvrdiť a doplniť archívne údaje.
V roku 1322 podáva františkán Simon Simeonis opis skupiny Cigánov, ktorí sa utáborili v jaskyniach a podlhovastých stanoch arabského typu na Kréte. V roku 1348 sa objavili zmienky o skupine Cingarje, ktorá sa v Srbsku zdržiavala do konca 13. storočia. Koncom druhej polovice 14. storočia sa potvrdzuje mnohonásobný rozptyl tohto kmeňa. Na ostrove Korfu sa vytvorilo cigánske lénum „feudum Acinganorum“, ktoré existovalo až do 19. storočia. Život obyvateľov s výnimkou trestu smrti závisel od ich „baróna“. V roku 1397 udelil benátsky guvernér na východnom pobreží Peloponézu privilégiá skupine Acingani.

Na západnom pobreží Peloponézu sa Cigáni usadili v Modone v roku 1384. V tomto období bol miestom imigrácie cigánskych skupín z Východu pravdepodobne Cyprus. Viacero oblastí ako napr. Epir v Grécku, kde sa tieto skupiny koncentrovali, sa nazývalo „Malý Egypt“, čo súviselo s ich reprodukciou. Je to bezpochyby dôvod, prečo nazývali Cigánov prichádzajúcich do európskych krajín Egypťanmi, čo im v upravenej forme zostalo až dodnes: napr. Gypsy v angličtine, Gitanos v španielčine. Disperzia cigánskych skupín pokračovala v 14. storočí aj vo Valašsku a v Čechách a do roku 1430 okrem severských krajín v celej západnej Európe. V období od r. 1407 do 1416 nachádzame v rôznych kronikách údaje o prítomnosti cigánskych skupín v Nemecku. V roku 1416 mesto Kronstadt v Transylvánii podarovalo „Pánovi Emausovi z Egypta a jeho 120 člennej skupine“ peňažné dary a proviant. Nasledujúci rok prechádzali cigánske skupiny cez hanzovné mestá v Sasku, Bavorsku, Hessensku a popri Švajčiarskych hraniciach. Premiestňovali sa v skupinách aj so ženami a deťmi. Na ich čele stál „šéf“, „knieža“, „gróf“, „kapitán“, či „vojvoda“. Vlastnili kone, niekedy vozíky na batožinu a nazývali sa kajúcnici alebo pútnici. Žili z almužien. Pravdepodobne v roku 1417 dal nemecký cisár Žigmund cigánskemu vojvodovi Ladislavovi, ktorý prechádzal krajinou asi so stočlennou skupinou, odporúčajúci list, ktorý ho mal chrániť a na základe ktorého mali skupinu v mestách a dedinách ríše dobre prijať. Žigmund bol aj český kráľ, a preto Cigánov, ktorí prichádzali z Čiech nazývali niekedy Bohémiens. Podobné odporúčania vlastnila aj iná asi stočlenná skupina so 40 koňmi, ktorá sa objavila v roku 1420 v Holandsku v meste Deventer.