1580s, "new-made," with implications of "foppish," from fangle (n.) "a new fancy, a novelty," based on newfangle "fond of novelty" (see newfangled).
fandango
fandom
fane
fanfare
fang
fangled
Fannie Mae
fanny
fantabulous
fantail
fantasia