Well, what is a jukebox? It's more than a device which automatically plays music in exchange for money. There has to be some means of selecting from a range of tunes. Several of the mechanical music machines shown in this topic do that. But surely a jukebox has to play phonographic recordings.
In 1889, Louis Glass and William S. Arnold placed a coin-operated Edison cylinder phonograph in the Palais Royale Saloon in San Francisco. It was an Edison Class M Electric Phonograph in an oak cabinet refitted with their patented coin mechanism. It had no amplification and patrons had to listen to the music using one of four listening tubes. In its first six months it made over $1000 and is often cited as the first significant jukebox.
Versions of this machine were soon available playing four or five cylinders but, in my books, did not yet amount to a jukebox, as they lacked tune selection. The first fully fledged jukebox, as far as I'm aware, must be the amazing Multiphone by the Multiphone Operating Co. of New York which appears to have been made between 1905 and 1908. This all mechanical box not only offered 24 selections, but had great elegance of form, which was to become the signature of fine jukeboxes.
The Regina Hexaphone (or Automatic Reginaphone) arrived shortly afterwards, in 1908. This one allowed the patron to select from six four minute cylinders. Unlike the Multiphone, it was made for resale, with around 8000 manufactured up until 1921. Bar electronic amplification and lighting effects, the jukebox had arrived.
Some early boxes:
Bussoz clockwork Bussophone of 1921
Mills Hi-Boy, 1928
Bussoz Bussophone, 1942