The nomads studied the societies they encountered with some care, and they made an effort to present themselves in terms readily comprehensible to western Europeans: as devout Christian pilgrims. Their information network was impressive. There was no concerted action against them because they carried letters of protection apparently issued by several princes, notably Sigismund, Holy Roman Emperor and king of Hungary. Thus when they arrived at towns and castles they were admitted by the city government, bishop or lord and, to cite one of the city chroniclers, they were "treated humanely". The explanation of the wandering life (it was said) lay in their abandonment of Christianity in favour of paganism some years earlier; when they reverted to the true faith they were subjected by their own bishops to the penance of spending seven years on pilgrimage. This explanation would recur many times in various forms, long after the first seven years had elapsed and seven years had stretched beyond 70. It was also said that they had chosen to exile themselves from their native land in commemoration of the flight of Joseph, Mary and the baby Jesus to Egypt, when Herod sought to kill the little boy. The Gypsies claimed to come from a place called "Lesser Egypt" in Africa (rather than from Asia), and they therefore were assumed to originate from somewhere near the Christian empire of Ethiopia, so they were welcomed by Emperor Sigismund as penitent Ethiopian pilgrims. The Ethiopian connection was exciting, because there was impossibly optimistic talk in the West of a grand crusading alliance between Catholic Europe and Ethiopia against the Muslim world. 

Through their supposed Egyptian origins they came to be known as Egypciens, and hence as "Gypsies"; this was an identity they seized upon, for the name had positive connotations. Yet there was always great ambivalence towards these nomads. In 1469 a "count of Little Egypt" was sent packing from Frankfurt-am-Main without gifts, and again and again the city council tried to keep Gypsies out of the town. Hospitality turned into hostility.

On August 17, 1427 they reached Paris. At their head was a single "duke", accompanied by a count and ten mounted men. An anonymous observer wrote: "they said that they were good Christians; they came from Lower Egypt." They elaborated the story of their origins still further. They now claimed that they had originally lived in a land that had become Christian, following its invasion by other Christians. Conquered by the Saracens, they had then abandoned their faith, only to become Christian once more when the Holy Roman Emperor and the king of Poland overran their land. The emperor was unhappy about their disloyalty and insisted that he would not allow them to return home without the consent of the pope. So they were sent to Rome, and the pope imposed a penance on them. They must wander the world for seven years without ever sleeping in a bed. Yet their harsh life was to be made less difficult to bear, since the pope ordered every bishop and abbot to give them a one-off gift of ten pounds in cash (thereby ensuring that they kept moving). The pope supposedly issued letters in their favour, though needless to say none has ever been found in the papal archives. 

The Parisian response to their arrival was to keep them outside the city walls, at Saint-Denis, even though they only numbered between 100 and 120. They became quite an attraction to the Parisian public. Most wore silver earrings, which they said was a sign of gentility in their homeland. In other words, they wanted to be recognised as people of high standing, despite their ragged clothes and simple style of life. The men were said to be "very black", with black frizzy hair and pony-tails. They wore the simplest clothes: a blanket above a long smock. They were fortune-tellers, sometimes sowing discord when they convinced men and women that they were being cuckolded by their spouse. News of their necromancy reached the bishop of Paris, who decided to put an end to this nonsense: he arrived and excommunicated the fortune-tellers along with those who believed their false claims. On September 8 the Gypsies, under pressure from the bishop, moved on. The negative image of the Gypsies thus goes back to their first arrival in western Europe 600 years ago.

The stigmatisation of the Gypsies on the supposition that they were criminals led to their further exclusion from society, making it impossible for them to settle and strengthening the stereotype that established itself across western Europe. Often, they passed themselves off as Greek Christians, for this elicited sympathy at a time when the Turkish threat to the Balkans was seen to be real. When columns of Gypsies claiming to be Greek exiles entered Spain at the end of the 15th century, they were entering a hornet's nest. The Jews had recently been expelled, and the Moors were under pressure to convert and to abandon their distinctive culture. Despite their claim to be Christian pilgrims, they could easily be confused with Moors, which would place them in great peril from the Inquisition and the public authorities. Yet what dismayed the rulers of Spain, Ferdinand and Isabella, was their conduct, not their supposed religious identity. The king and queen issued an ordinance to the wandering "Egyptians", in which they complained that the Gypsies had sustained themselves not from honest crafts but from begging, stealing and fortune-telling. They were ordered to settle down and to find a master for whom they could work. Otherwise they would have to leave the country.