There are some myths and legends attached to this signal. The one most frequently heard has Admiral "Bull" Halsey sending it to ships of Task Force 38 during World War II. He could not have done this, since the signal did not exist at that time.
"Bravo Zulu" actually comes from the Allied Naval Signal Book (ACP 175 series), an international naval signal code adopted after the North Atlantic Treaty Organization (NATO) was created in 1949. Until then, each navy had used its own signal code and operational manuals. World War II experience had shown that it was difficult, or even impossible, for ships of different navies to operate together unless they could readily communicate, and ACP 175 was designed to remedy this.
In the U.S. Navy signal code, used before ACP 175, "well done" was signaled as TVG, or "Tare Victor George" in the U.S. phonetic alphabet of that time. ACP 175 was organized in the general manner of other signal books, that is, starting with 1-flag signals, then 2-flag and so on. The 2-flag signals were organized by general subject, starting with AA, AB, AC, ... AZ, BA, BB, BC, ... BZ, and so on. The B- signals were called "Administrative" signals, and dealt with miscellaneous matters of administration and housekeeping. The last signal on the "Administrative" page was BZ, standing for "well done."
At that time BZ was not rendered as "Bravo Zulu," but in each navy's particular phonetic alphabet. In the U.S. Navy, BZ was spoken as "Baker Zebra." In the meanwhile, the International Civil Aviation Organization (ICAO) had adopted English as the international air traffic control language. They developed a phonetic alphabet for international aviation use, designed to be as "pronounceable" as possible by flyers and traffic controllers speaking many different languages. This was the "Alpha, Bravo, Charlie, Delta..." alphabet used today. The Navy adopted this ICAO alphabet in March 1956. It was then that "Baker Zebra" finally became "Bravo Zulu."