early 14c., clogge "a lump of wood," origin unknown. Also used in Middle English of large pieces of jewelry and large testicles. Compare Norwegian klugu "knotty log of wood." Meaning "anything that impedes action" is from 1520s, via the notion of "block or mass constituting an encumbrance."
The sense of "wooden-soled shoe" is first recorded late 14c.; they were used as overshoes until the introduction of rubbers c. 1840. Originally all of wood (hence the name), later wooden soles with leather uppers for the front of the foot only. Later revived in fashion (c. 1970), primarily for women. Clog-dancing "dancing performed in clogs" is attested from 1863.