Kariera Wkrótce po skończeniu szkoły został pierwszym i jedynym iluzjonistą, któremu rząd kanadyjski przyznał stypendium na studiowanie sztuk magicznych; był to zresztą jeden z warunków jego otrzymania. Dzięki finansowemu wsparciu podróżował po świecie i uczył się od najlepszych iluzjonistów tamtych czasów, m.in. Dai Vernona i Slydiniego, którego uważał za swojego najważniejszego nauczyciela magii.
Chcąc przywrócić sztukom magicznym minione „dni sławy”, Henning ciągle doskonalił swój kunszt. Dzięki zebranym funduszom rozwinął swój spektakl Spellbound. Wspólnie z reżyserem Ivanem Reitmanem, kompozytorem Howardem Shore i aktorką Jennifer Dale, stworzył musical, który łączył w sobie dramatyczną historię i magiczne sztuczki. Początkowo wystawiano go w Toronto, gdzie bardzo szybko zdobył ogromną popularność. Następnie przeniesiono go do broadwayowskiego Cort Theatre w Nowego Jorku i wystawiano pod nazwą The Magic Show. Tam spektakl również odniósł ogromny sukces i doczekał się ponad tysiąca dziewięciuset przedstawień. Został też piątym najdłużej granym musicalem na Broadwayu lat siedemdziesiątych, a Henningowi dał nominację do nagrody Tony Award.