Although Herbert's reputation lies with his operettas, he also composed two grand operas. He searched for several years for a libretto that appealed to him, finally finding one by Joseph D. Redding called "Natoma" that concerned a historical story set in California. He composed the work from 1909 to 1910, and it premiered in Philadelphia on February 25, 1911 with soprano Mary Garden in the title role and the young Irish tenor John McCormack in his American operatic debut. Herbert's score was well received, and the opera was repeated as part of the company's repertory during the next three seasons. It also enjoyed performances in New York City, making its debut there on February 28, 1911. Herbert's other opera, "Madeleine", was a much lighter work in one act. On January 24, 1914, it had its premiere at the Metropolitan Opera, but it was not revived beyond that season.