1745, from American Spanish (where it is attested by 1598), probably from Yavapai (a Yuman language) 'epache "people." Sometimes derived from Zuni apachu "enemy" (see F.W. Hodge, "American Indians," 1907), but this seems to have been the Zuni name for the Navajo.
In French, the sense of "Parisian gangster or thug" first is attested 1902, said to have been coined by journalist Victor Moris; it was in English by 1908. Apache dance was the World War I-era equivalent of 1990s' brutal "slam dancing." Fenimore Cooper's Indian novels were enormously popular in Europe throughout the 19c., and comparisons of Cooper's fictional Indian ways in the wilderness and underworld life in European cities go back to Dumas' "Les Mohicans de Paris" (1854-1859). It is probably due to the imitations of Cooper (amounting almost to plagiarisms) by German author Karl May that Apaches replaced Mohicans as the quintessential savages in European popular imagination. Also compare Mohawk.