In 1322, the Franciscan Simeon Simeonis met Rroma in Crete, in 1348 and 1362, we have writings about Czingarije in Serbia and in Croatia. Rroma stayed in the Balkan up to the Turkish invasions.
This by far doesn't mean that Rroma only appeared in the Byzantine Empire around that time. On the contrary, Rroma had already been there for quite a while. They most probably arrived in the Balkan, especially in Thrace, before the turn of the first millenium. How they arrived is by far not clear, but the most probable explanation is that they were deported together with the Armenians to those regions following the defeat of the Paulicians by the Byzantine forces. The name they were given, Athinganoi, corresponds to the one of a sect that was often associated, at least during Byzantine times, with the Paulicians.
One has to stress that there are many documents from the XIII and XIV the centuries which may refer to Rroma and their presence in various European countries. It is, unfortunately not easy to decide whether this is the case or not. We have chosen to refer to documents from which one can infer they refer to Gypsies. Many experts do think that when Rroma arrived in the Balkan and in nearby countries, many of them found work as blacksmiths as well as in other trades, that the autochthonous population needed the Rroma workers and their trades. For that reason, most Rroma settled in those countries, built their houses, villages and Rroma quarters (mahalades) and stopped travelling.