The first documented use of a substitution cipher for military purposes appears in Julius Caesar's Gallic Wars. Julius Caesar used one type of substitution cipher in which he simply replaced each letter in the message with the letter that is three places further down the alphabet. This type of substitution has come to be known as a Caesar shift cipher, or additive cipher.
If I sent "ZDUQLQJ," the receiver would know I mean "WARNING."
Perhaps you have seen a popular tool to aid in building a Caesar cipher. This device (pictured below) is known as a Caesar shift wheel. The outer circle (green) is the plaintext alphabet. The inner circle (purple) can rotate giving different possible ciphertexts.
This form of substitution cipher was used by military leaders for centuries after Caesar and was thought to be un-crackable. However, the Arabs developed a system that could decipher a Caesar cipher (along with other substitution ciphers) with relative ease. More information on how you can break a Caesar cipher (and other substitution ciphers) can be found here: Cryptanalysis