De Lucía syntyi AndalusiassaAlgecirasin kaupungissa ja oli viidestä sisaruksesta nuorin. Taiteilijanimensä hän valitsi äitinsä Lucía Gómezin kunniaksi. Paco de Lucía oli merkittävää muusikkosukua: hänen isänsä Antonio Sánchez ja veljensä Ramón de Algeciras olivat flamencokitaristeja, ja veli Pepe de Lucía on flamencolaulaja. De Lucía esiintyi julkisesti ensimmäisen kerran 11-vuotiaana Radio Algecirasissa, ja seuraavana vuonna hän sai kunniamaininnan Jerezin flamencokilpailussa. Vuonna 1961 hän oli kiertueella tanssija José Grecon kanssa, ja vuosina 1968–1977 hän työskenteli merkittävän flamencon uudistajan laulaja Camarón de la Islan kanssa ja he äänittivät yhdessä kymmenen albumia.[2]