After serving in World War II, Denny returned to Los Angeles where he studied piano and composition under Dr. Wesley La Violette and orchestration under Arthur Lange at the Los Angeles Conservatory of Music. He also studied at the University of Southern California.
In January of 1954, Don the Beachcomber's (which later became Duke Kahanamoku's) brought Denny to Honolulu, Hawaii. He performed here for ten years, forming his own combo in 1955 and signing to Liberty Records. The original combo consisted of Augie Colon on percussion and birdcalls, Arthur Lyman on vibes, John Kramer on string bass, and Denny on piano. Lyman soon left to form his own group and future Herb Alpert sideman and Baja Marimba founder Julius Wechter replaced him. Harvey Ragsdale later replaced John Kramer.
Denny described the music his combo plays as "window dressing, a background". It is the perfect compliment to the exotic setting of Hawaii. "A lot of what I'm doing", he stated in Incredibly Strange Music Volume 1 "is just window dressing familiar tunes. I can take a tune like "Flamingo" and give it a tropical feel, in my style In my arrangement of a Japanese farewell song, "Sayonara", I include a Japanese three stringed instrument, the shamisen. We distinguished each song by a different ethnic instrument, usually on top of a semi-jazz or Latin beat Even though it remained familiar, each song would take on a strange, exotic character." Denny built a collection of strange and exotic instruments from several airline friends. They would bring Denny back these instruments and he would build arrangements around them. His music was a combination of ethnic styles: South Pacific, the Orient and Latin rhythms. It is the music a lot of people believed came from the islands. A musical fantasy created by Denny.
During an engagement at the Shell Bar, Denny discovered what would become his trademark and the birth of "Exotica". The bar had a very exotic setting: a little pool of water right outside the bandstand, rocks and palm trees growing around, very quiet and relaxed. As the group played on night, Denny became aware of bullfrogs croaking. The croaking blended with the music and when the band stopped, so did the frogs. Denny thought this to be a coincidence, but when he tried the tune again later, the same thing happened. This time, his bandmates began during all sorts of tropical bird calls as a gag. The band thought it quite amusing, but as nothing more than a joke. The next day, though, someone approached Denny and asked if he would do the arrangement with the birds and frogs. While at first he thought it was ridiculous, the more Denny thought about it, the more it made sense. At rehearsal, he had the band do "Quiet Village" with each doing a birdcall spaced apart.. Denny did the frog part on a grooved cylinder and the whole thing became incorporated into the arrangement. It caught on like wildfire and everyone wanted to hear "Quiet Village".
The seminal "Exotica" album was recorded in the Webley Edwards Studio (not, as often reported, the Aluminum Dome at Henry I. Kaiser's Hawaiian Village Complex) in Waikiki in November of 1956. In 1958, Dick Clark hosted Denny on American Bandstand. "Quiet Village" reached #2 on Billboard's charts in 1959 with the "Exotica" album reaching #1. He rode the charts of Cashbox and Variety also. Denny had as many as three or four albums on the charts simultaneously during his career. He also had national hits with "A Taste of Honey", "The Enchanted Sea", and "Ebb Tide".