c. 1300, "foreign lands" (especially non-Christian lands), from Latin barbaria "foreign country," from barbarus "strange, foreign" (see barbarian (n.)). Meaning "Saracen nations on coastal North Africa" is attested from 1590s, via French (Old French barbarie), from Arabic Barbar, Berber, ancient Arabic name for the inhabitants of North Africa beyond Egypt.
Perhaps a native name, perhaps an Arabic word, from barbara "to babble confusedly," but this might be ultimately from Greek barbaria. "The actual relations (if any) of the Arabic and Gr[eek] words cannot be settled; but in European langs. barbaria, Barbarie, Barbary, have from the first been treated as identical with L. barbaria, Byzantine Gr[eek] barbaria land of barbarians" [OED].