Sytuacja Romów w Bizancjum zaczęła się pogarszać wraz ze wzrostem potęgi Turków i związanego z nim poczucia zagrożenia. Romowie zaczęli być postrzegani jako obcy przybysze, którzy z racji pobytu w Azji Mniejszej mogli mieć kontakty z Turkami i służyć im jako szpiedzy. Dlatego już od XIII w. Romowie zaczynają się na Bałkanach przenosić coraz bardziej na północ: do Serbii, Bułgarii, Mołdawii i Wołoszczyzny. W tych dwóch ostatnich krainach Romowie stopniowo zamieniani są w niewolników, najpierw w dobrach kościelnych a następnie w prywatnych. Pozostali stawali się własnością państwa. O ile dwie pierwsze grupy były przymusowo osiedlane w kościelnych lub prywatnych dobrach, o tyle niewolnicy państwowi przenosili się z miejsca na miejsce w zależności od zapotrzebowania na siłę roboczą. Niewolnictwo na ziemiach rumuńskich (formalnie zniesione dopiero w połowie XIX w.) stanowiło bardzo ważny okres w historii Romów. Wiele podziałów grupowych bierze swój początek od różnych rodzajów prac, do których używano Romów. Również postawy otoczenia wobec Romów ukształtowały się w owym czasie, a słowo „Tigan” stało się w języku rumuńskim synonimem niewolnika.

Romowie, którzy pozostali na Bałkanach, dostawali się stopniowo w sferę wpływów tureckich. Inni ruszyli na północ, osiągając pod koniec XIV w. tereny królestwa Węgier, gdzie część z nich osiedliła się (głównie na terenach Słowacji, gdzie istniało duże zapotrzebowanie na usługi dostarczane przez Romów), część zaś ruszyła dalej poprzez Polskę (gdzie pierwsze wzmianki o Romach pochodzą z 1401 r.) i Czechy do Europy Zachodniej. Alternatywna droga do Europy zachodniej mogła prowadzić przez Półwysep Apeniński, z wykorzystaniem morskich szlaków, nad którymi sprawowała kontrolę Republika Wenecka.

Pojedyncze grupy romskie przenikają do Europy Zachodniej od końca XIV wieku, są jednak trudno zauważalne z racji znikomej liczebności i przyjętej strategii nie rzucania się w oczy. Sytuacja ta zmienia się w początkach trzeciej dekady XV w., kiedy to Romowie stają się widoczni, poruszając się w dużych i bogatych orszakach pod wodzą przywódców określanych jako „hrabiowie” lub „książęta”, ogłaszając swoje przybycie do miast, spotykając się z przedstawicielami władzy i uzyskując od nich „dokumenty podróżne” uprawniające do poruszania się na danym terenie i uzyskiwania pomocy. Ta nowa strategia, określana jest w literaturze jako „wielki podstęp”. Była ona oparta na wiedzy o obyczajowości i strukturze społecznej średniowiecznej Europy. Jej elementem było wykorzystywanie motywów religijnych, polegające na przedstawianiu się jako pokutujący za grzechy pielgrzymi.

Strategia ta przynosiła początkowo sukcesy i umożliwiła bardzo szybkie rozprzestrzenienie się Romów po Europie. W latach 1416-1420 pojawiają się na ziemiach niemieckich, holenderskich i w Szwajcarii. W roku 1422 w północnej części Półwyspu Apenińskiego. W latach 1419-1427 we Francji. W latach 1425-1470 w Hiszpanii i Portugalii. W latach 1470-1505 w Anglii i Szkocji. Można więc powiedzieć, że od końca XV i początku XVI w. Romowie są już w całej Europie.

Stosunek do pierwszych romskich przybyszów był w Europie zachodniej w miarę pozytywny. Ich sposób życia nie był bynajmniej czymś wyjątkowym w ówczesnej Europie, w której żyło wielu wędrownych „ludzi gościńca”, jałmużna była traktowana jako chrześcijański obowiązek a pokutna pielgrzymka byłą czymś samo przez się zrozumiałym. Co ciekawe, najwcześniejsze źródła pisane nie wspominają o jakiejś radykalnej odrębności Romów: rasowej, kulturowej czy językowej. Nie byli też postrzegani przez Kościół jako konkurencja dla chrześcijaństwa i w związku z tym nie spotykali się z religijną nienawiścią – tak jak Żydzi. Byli raczej traktowani jak poganie, których należy ewangelizować. 

Problemy pojawiały się w sferze ekonomii: w odróżnieniu od Europy wschodniej, na Zachodzie nie było tak wielkiego zapotrzebowania na romskie towary i usługi, zaś rynek był zorganizowany i niezbyt przychylny nowym podmiotom. Stąd też w Europie zachodniej Romowie częściej musieli być mobilni by aktywnie poszukiwać odbiorców, podczas gdy w Europie wschodniej prowadzili oni częściej życie osiadłe. Mobilność nie eliminowała jednak konfliktów, które narastały zwłaszcza tam, gdzie pojawiały się większe grupy romskie – stąd kultywowany w grupach wędrownych aż do XX w. zwyczaj rozpraszania się w celu niezwracania uwagi otoczenia. 

Już pod koniec XV wieku nastawienie do Romów zmienia się na gorsze i w pierwszej połowie XVI wieku zamienia się w ciąg prześladowań. Początkowo prześladowania te były niezorganizowane, lokalne i chaotyczne, później zaś coraz bardziej scentralizowane i planowe. Romowie byli oskarżani o szpiegostwo, praktyki pogańskie i czary, a także cierpieli z powodu regulacji skierowanych przeciwko włóczęgom i żebrakom. Coraz częstsze były też konflikty z cechami rzemieślniczymi, dla których wędrowni romscy rzemieślnicy stanowili konkurencję. Zaczęto wprowadzać w życie edykty antycygańskie i deportować Romów, najpierw do innych krajów europejskich (np. wypędzenie Romów z Anglii do Skandynawii, czy z Hiszpanii do Portugalii), a później do kolonii zamorskich, gdzie starano się umieszczać „elementy niepożądane”. Pionierami deportacji kolonialnych byli Portugalczycy, którzy już w pierwszej połowie XVI w. deportowali Romów do kolonii w Afryce. W XVII w. stało się to powszechną praktyką , zwłaszcza jeśli chodzi o romskie kobiety, mające zapewnić „równowagę płci” w koloniach (Romów mężczyzn skazywano raczej na galery).

W tymże stuleciu rozpoczęły się też deportacje Romów do Brazylii. Hiszpania deportowała swoich Romów do Afryki północnej, natomiast z rozmaitych powodów zabraniała wysyłania ich do Ameryki. Takich skrupułów nie miała Francja, a zwłaszcza Anglia. Jednocześnie sami Romowie podejmowali często decyzję o ucieczce przed prześladowaniami do bardziej wówczas liberalnej i tolerancyjnej Europy środkowej i wschodniej, w tym do Polski. Taka jest na przykład geneza grup Polska Roma i Ruska Roma, wywodzących się z uciekinierów z ziem niemieckich, którzy znaleźli warunki do życia w Królestwie Polskim i Rosji.

Równolegle do deportacji w krajach Europy zachodniej stosowano praktyki dyscyplinujące i asymilacyjne, częstokroć zakrojone na bardzo szeroką skalę, jak na przykład w monarchii Habsburgów. W całej Europie, zwłaszcza zaś w państwach najbardziej rozwiniętych, Romowie dostają się w tryby nowoczesnego społeczeństwa i jego strategii dyscyplinujących, których celem jest między innymi zatrzymanie romskich migracji i zwiększenie kontroli instytucji władzy nad populacją. O ile jednak dążenie do kontroli pozostało cechą charakterystyczną stosunku państwa do Romów, o tyle nacisk na asymilację stopniowo malał w XIX w., częściowo z powodu kosztów i niewielkich osiągnięć stosowanych strategii, częściowo zaś z powodu rosnącej popularności teorii rasowych, zgodnie z którymi ludzie są zdeterminowani przez swą biologiczną naturę, której nie można zmienić żadnymi programami asymilacyjnymi.