Madeline and the Gypsies first came to Bemelmans in 1956 (he then called it Madeline and the Circus) and he had a draft completed the following year. He traveled around France researching small Gypsy circuses filling volumes of notebooks with his sketches and observations. The first published version of the story appeared in the Christmas 1958 issue of McCall's. He completed the book the following February.

The following are excerpts from those circus journals.

"Followed a small, or rather two small circuses along the coast for the last 5 days. They travel in short distances, about 10 kilometers a day, from one patch to another. The larger of these has ponies and dogs and a monkey as he is seen in the Picasso drawing 'a Pavian' . The dogs are billed as the 'Chiens Chanteurs' and they bark of all songs: "OH SUSANNAH", that is , the man points to this or that dog and the six of them, from basso to soprano, bark it to the accompaniment of an Orgue de Barbary.

"The performers are all elegant. The clothes they wear, very beautiful, not so much from choice of colors but because bought second hand, and worn now to shreds, they have all faded hues. "...to my happy surprise found that babies even perform, not only children. This is an open air circus without tent, seats spectators on three rows of benches, has a ring 25 feet in diameter, filled with sawdust. In morning practice, the father laying on his back and doing stunts with 4 year old and 5 year old, baby puts the wooden chips (rather than sawdust) on his chest, which then the olders clean off. Animals: ponies, a trained goat, a monkey." "The audience are 90% children by themselves, or in arms, the people bring babies. The worst acts are applauded."

In "Madeline and the Gypsies", the lion skin plays a pivotal role. The Gypsy Mama zips Madeline and Pepito up in an old lion skin to hide them from Miss Clavell. However, Bemelmans tried several variations on this idea.

"There is one flaw, in the story now, and caught by some children when one tries it out on them and that is the appearance of the Lion skin - where did it come from, why is it there - and I have worked on the problem - also I don't think the sequence of the Lion ripping the cage off, is good enough. I have now in mind, to put an old Lion into the circus - who in one town walks away, and goes to a restaurant, where just a side of beef is being carried inside. Or he sits down in the chair and grabs a steak from someone-

He took some meat
Which was destined for other teeth--

Police come and shoot him dead--
Just as he wiped his mouth with bread

(and for a week they eat Lion meat--at the circus)

And every day the children cried--
while Leos skin hung there and dried-"

(from a different note) "Instead of the Police, it could also be the French Sauce that killed the Lion, who used to have his diet simple - would be better - "

(from a later note) "In order to justify the Lion skin, did a completely new scenario, with the Lion part of the circus, and then doing his tricks, and on the way looking out of the cage seeing sheep, butcher shops and getting hungrier and hungrier, and one night escaping and invading a Restaurant where he eats off the tables. 1. It was too long. 2. Not in the mood of the children's book. 3. It did nothing to make it more logical.

Decided then that when children first come to circus, the old Gypsy woman pulls stuff from a trunk to fit them, and it is filled with all kinds of things, a kind of stage trunk and from this she also pulls the lion skin later on. That is all that is needed."

"Along these lions, I mean lines, It will make it a perfect story. I knew something was missing but not what. Therefore it's a good thing - (Barbara take notice) to let a thing lay around - after it's too late to repair it when it is in print."