Off with his head

Shakespeare used the phrase many times in his plays and I can find no record of any earlier usage; for example, in Henry VI Part III, 1592:

QUEEN MARGARET:
Off with his head, and set it on York gates;
So York may overlook the town of York.

Lewis Carroll became the best-known user of the phrase when he included it in Alice’s Adventures in Wonderland, (published 1865), The Queen of Hearts shrieks the phrase several times in the story – in fact she doesn’t say a great deal else:

The players all played at once without waiting for turns, quarrelling all the while, and fighting for the hedgehogs; and in a very short time the Queen was in a furious passion, and went stamping about, and shouting’ Off with his head!’ or ‘Off with her head!’ about once in a minute.