Stentoft was born in Holbæk, where he graduated from the Stenhus Kostskole (now Stenhus Gymnasium og HF [da]).

Initially, he planned to study law, but due to lack of money, he started to compose music for commercials.

In 1934, he began working as an accompanist and composer for the revue troupe Co-Optimisterne.

A lot of his tunes quickly achieved widespread popularity, and he earned good money by composing and, later on, by producing revues.

During his career, Stentoft also managed various theatres: Frederiksberg Teater (now Aveny-T [da]) in Frederiksberg and three theatres in Copenhagen, Dagmar Teatret [da], Det Ny Scala and Apolloteatret [da].