Douglas Harper's Etymology Dictionary
1520s, deformed (by influence of stark (adj.)) from Middle English start naked (early 13c.), from Old English steort "tail, rump," from Proto-Germanic *stertaz (cognates: Old Norse stertr, Danish stjert, Middle Dutch stert, Dutch staart, Old High German sterz, German Sterz), from PIE *sterd-, extended form of root *ster- (1) "stiff, rigid, firm, strong" (see stereo-). Hence British slang starkers "naked" (1923).
Usage examples of "stark-naked".
Sleep imperceptibly took advantage of this happiness and relief but now, in sleep, there was no rest at all, for sleep consisted of sixty-four squares, a gigantic board in the middle of which, trembling and stark-naked, Luzhin stood, the size of a pawn, and peered at the dim positions of huge pieces, megacephalous, with crowns or manes.
Changing her crinolines, silks and powdered peruke for the polished riding boots, thorax strappings and black gauntlets, she decided to go down to the holding chamber to view the two newcomers who were chained stark-naked to the wall.