c. 1300, clete "a wedge," from Old English *cleat "a lump," from West Germanic *klaut "firm lump" (source also of Middle Low German klot, klute, Middle Dutch cloot, Dutch kloot, Old High German kloz, German kloß "clod, dumpling").
In Middle English, a wedge of wood bolted to a spar, etc., to keep it from slipping (late 14c.). Meaning "thin metal plate fastened under a shoe, etc." (originally to preserve the sole) is from c. 1825, originally a dialect word. The athletic cleat, for gripping, is attested from 1904.