The Romans called them "puellae Gaditanae" and appreciated their dancing skills. Lord Byron praised (one of them) in a poem, Luis Mariano did the same in a song. Where in Spain do these "belles" hail from?

Well, Mr. Flamingo, I don't have time to do justice to this question, but...

It must be Flamenco dancers you have in mind, from Cadiz.
https://en.wikipedia.org/wiki/Flamenco

The Romans called them The Dancing Girls from Cadiz.
https://www.jstor.org/stable/643110

"Luis Mariano was a Spanish Basque popular tenor who reached celebrity in 1946 with « La belle de Cadix » (« The Beautiful Lady of Cadix ») an operetta by Francis Lopez."
http://www.answers.com/topic/luis-mariano

And Byron wrote "Girl of Cadiz."
http://readytogoebooks.com/LB-GOC-P60.html

Flaming Flemings, huh? From what I heard the flamingo birds were named after the Flemish merchants who in Middle Ages caught the eye of the Spaniards and Italians with their excessively coloured dress. In Roman times however what the Belles de Cadiz danced cannot have been called the Flamenco yet because we still had to be invented and our area was the territory of the Morini and Menapii, all "marsh-dwellers" well at ease in the creeks, sea-inlets, "bayous" of what is now Northern France and North-Belgium. http://www.yourdictionary.com/flamingo

But, what's a little anachronism among friends?

You're right, of course, and I hurriedly came up with the first bit, not intending to look up the rest, but couldn't quit.

"The first time flamenco is mentioned in literature is in 1774 in the book Cartas Marruecas by José Cadalso."

So, no flamenco, flamingos, or Flemish allowed.

https://en.wikipedia.org/wiki/Flamenco

It may be worth mentioning in this context that "Flemish" is in itself more a geographic than a linguistic term. The rootword 'Flandr' refers to 'flooding': land that is daily partially flooded by high tide and therefore difficult to penetrate fro invading armies. There always have been francophones within the County of Flanders, the Count of Flanders and a large part of the aristocracy were French-speakers. Only we were not on very good terms with "Paris" and the French King. And by the way we were there at the Battle of Hastings, and William the Conqueror 's Queen was not unfamilar with the Flemish floodlands.
https://en.wikipedia.org/wiki/Flemish#Etymology