1520s, from bare (adj.) + -headed.
bare
bareback
barefaced
barefoot
bare-handed
bare-headed
barely
bareness
barf
barfly
bargain