The expression “caught red handed” has its origins in Scotland around the 15th century. Given how it was used in the earliest references, the phrase “red hand” or “redhand” probably referred to people caught with blood on their hands from murder or poaching.
The first documented mention of “red hand” is in the Scottish Acts of Parliament of James I, written in 1432:
That the offender be taken reid hand, may be persewed, and put to the knawledge of ane Assise, befoir the Barron or Landeslord of the land or ground, quhidder the offender be his tennent, unto quhom the wrang is done or not… And uthers not taken reid hand, to be alwaies persewed befoir the…
It subsequently popped up numerous times in various legal proceedings in Scotland, nearly always referring to someone caught in the act of committing some crime, such as “apprehended redhand” or “taken with redhand."
The first documented instance of the expression morphing from “red hand” to “red handed” was in the early 19th century work Ivanhoe, written by Sir Walter Scott:
I did but tie one fellow, who was taken redhanded and in the fact, to the horns of a wild stag.
Its use in Ivanhoe subsequently helped popularize it throughout the English speaking world.
"Caught red handed” made its debut in Guy Livingstone, written by George Alfred Lawrence and published in 1857:
My companion picked up the object; and we had just time to make out that it was a bell-handle and name-plate, when the pursuers came up – six or seven “peelers” and specials, with a ruck of men and boys. We were collared on the instant. The fact of the property being found in our possession constituted a ‘flagrans delictum’ – we were caught red-handed.