Once upon a time, there were no messengers. Then the worlds was invented and blam! there were messengers and general contractors. It just worked that way.
In the beginning, messengers had a fairly easy job: the most complicated message they delivered was “Ughhhggguhi” and since no one knew what that meant no one cared much whether the message got delivered verbatim (ver-grunt-im?) or not.
Not too long after that, people started using actual words to communicate. At that point, messages began to matter.
And the role of messenger became much riskier.
The first time the phrase “Don’t kill the messenger” was used was when Joe Neanderthal decided to stay out with the boys after the hunter and sent his son Thnng to tell Mrs. Joe Neanderthal not to wait up for him. Mrs. Joe did not react well to the message, leading her to stop, drop, roll far away, and mumble (but very quietly) “Not my fault—don’t kill the messenger.”
Shortly thereafter (if you’re a fan of condensed evolution), Plutarch wrote about not shooting the messenger, but since no one really understood him, everyone waited until Sophocles got around to writing “no one loves the messenger who brings bad news” in Antigone. [There will not be a quiz. You’re welcome.]
Shakespeare used a variation on the phrase in both Henry IV and Antony and Cleopatra.
On the more authentic military side, there was an unwritten code of conduct in which messengers (known in war as emissaries so they could get better uniforms) were received and sent back (unharmed) with messages generally designed to confuse everyone involved.