Los cifrados utilizados en los criptogramas no fueron creados originalmente para fines de entretenimiento, sino para el cifrado real de secretos militares o personales.
El primer uso del criptograma con fines de entretenimiento ocurrió durante la Edad Media por monjes que tenían tiempo libre para juegos intelectuales. Un manuscrito encontrado en Bamberg afirma que a los visitantes irlandeses de la corte de Merfyn Frych ap Gwriad (fallecido en 844), rey de Gwynedd en Gales, se les dio un criptograma que solo podía resolverse transponiendo las letras del latín al griego. Alrededor del siglo XIII, el monje inglés Roger Bacon escribió un libro en el que enumeraba siete métodos de cifrado, y afirmó que «un hombre está loco que escribe un secreto de cualquier otra manera que no sea uno que lo oculte de lo vulgar. En el siglo XIX, Edgar Allan Poe ayudó a popularizar los criptogramas con muchos artículos de periódicos y revistas.
Ejemplos conocidos de criptogramas en la cultura contemporánea son los puzzles de periódicos sindicados Cryptoquip y Cryptoquote, de King Features.
En un desafío público, el escritor J. M. Appel anunció el 28 de septiembre de 2014 que la página de índice de su colección de cuentos, Scouting for the Reaper, también se duplicó como criptograma, y prometió un premio para el primero en resolverlo.