c. 1300, "incantation, magic charm," from Old French charme (12c.) "magic charm, magic spell incantation; song, lamentation," from Latin carmen "song, verse, enchantment, religious formula," from canere "to sing" (from PIE root *kan- "to sing"), with dissimilation of -n- to -r- before -m- in intermediate form *canmen (for a similar evolution, see Latin germen "germ," from *genmen). The notion is of chanting or reciting verses of magical power.
A yet stronger power than that of herb or stone lies in the spoken word, and all nations use it both for blessing and cursing. But these, to be effective, must be choice, well knit, rhythmic words (verba concepta), must have lilt and tune; hence all that is strong in the speech wielded by priest, physician, magician, is allied to the forms of poetry. [Jakob Grimm, "Teutonic Mythology" (transl. Stallybrass), 1883]
Sense of "pleasing quality, irresistable power to please and attract" evolved by 17c. From 1590s as "any item worn to avert evil;" meaning "small trinket fastened to a watch-chain, etc." first recorded 1865. Quantum physics sense is from 1964. Charm-bracelet is from 1941; charm-school from 1919. To work like a charm (figuratively) is recorded by 1824.