Paso Doble este cel mai misterios dintre toate dansurile sportive. Nu există foarte multe informaţii legate de istoria acestui dans, iar despre originea sa se pot face doar supoziţii. Un lucru este însă cert: conţine paşi simpli, de marş
Una din presupusele origini ale acestui dans ar putea fi marşul francez denumit „Pas redouble”. Acest marş era scris în măsura de 2/4 şi avea un ritm de circa 130 bătăi pe minut.
Probabil că numele de „Paso Doble” are ca origine ritmul binar al muzicii şi faptul că fiecărei bătăi muzicale îi este alocat un pas. Cu toate acestea, mai este cunoscut şi sub numele de „Spanish One Step” din cauza acelui unic pas care se face pe fiecare bătaie a muzicii.
În Spania acest gen de muzică mai este cunoscut şi sub numele de „El Soleo” şi este interpretat în timpul coridelor. La graniţa cu Spania, în Sudul Franţei, în 1910, profesorii de dans francezi au avut ideea de a aduce atmosfera coridei în saloanele de dans şi, astfel, au început să inventeze figuri de dans care imitau (bineînţeles într-o manieră stilizată) acţiunea din arenele iberice. Acestor influenţe franceze li se datorează şi denumirile unor figuri de dans consacrate, precum: Sur Place, Appel, Huit şi La Passe. Tot profesorilor de dans francezi trebuie să li se acorde creditul de a fi introdus în coregrafiile de Paso Doble şi elemente din alte dansuri spaniole, cum ar fi Fandango şi Rumba, dar mai ales Flamenco.
Acesta din urmă, aşa cum îl cunoaştem noi astăzi, îşi are originea în cafenelele, teatrele, sălile de bal din cartierul Triana din Sevilla şi a fost influenţat de Fandango, de baladele spaniole, de Tangoul negrilor şi de Guajira caraibiană. Flamenco este o formă de artă caracteristcă sudului Spaniei (Andaluzia) şi se prezintă în trei variante: Cante (cantec), Baile (dans) şi Guitarra (cântatul la chitara).