В сети есть хорошая работа: Дьячок М.Т. Цыганский язык и глоттохронология.
Из неё видно, что цыганский язык выделился из общеиндийского массива не позднее 100 г. до н.э.
Но это ещё не дата миграции: в Индии существует и множество других этнических групп, прекрасно уживающихся друг с другом.
Кроме того, в Таджикистане существует этническая группа люли, по языку родственная цыганам, но себя с ними не идентифицирующая (цыгане их тоже за своих не считают) - возможно, это след самых ранних этапов миграции.
Впервые цыгане засвидетельствованы в Византии, причём там их положение было довольно привилегированным. Ясно, что в Византии они не могли появиться раньше, чем появилась сама Византия.