mid-13c., from red (adj.1) + head (n.). Red (adj.), of persons, "having red hair" is from late Old English. Both Cain and Judas formerly were reputed to have had red or reddish-yellow beards.
The Carrot pate be sure you hate, for she'l be true to no man,
But put her too 't and she will do 't, and oft turns very common:
She that is red upon the head will doubtless ne'r forsake it,
But wanton be, assuredly, and willingly will take it.
["The True Lover's Admonition," Roxburghe Ballads, c. 1680]