Substitution ciphers are among the earliest methods of encryption. Examples of classic substitution ciphers include the well-known simple substitution and the less well-known homophonic substitution. Simple substitution ciphers are indeed simple, both in terms of their use and their cryptanalysis. Homophonic substitutions—in which a plaintext symbol can map to more than one ciphertext symbol—are also easy to use, but far more challenging to break. Even with modern computing technology, homophonic substitutions can present a significant cryptanalytic challenge. This article focuses on the design and implementation of an efficient algorithm to break homophonic substitution ciphers. The authors employ a nested hill climb approach that generalizes the fastest known attack on simple substitution ciphers. They test their algorithm on a wide variety of homophonic substitutions and provide success rates as a function of both the ciphertext alphabet size and ciphertext length. Finally, they apply their technique to the “Zodiac 340” cipher, which is an unsolved message created by the infamous Zodiac killer.