Het lied van de woestijn is een operette vol romantiek, sterke speelscènes en humor. Een Frans officier, Pierre Birabeau, kan de terreur, bedreven door de Franse troepen in Marokko, niet verdragen. Hij wordt hoofdman van een bende rovers om gezamenlijk het onrecht te bestrijden. Hij krijgt de bijnaam van "De Rode Schaduw". Alleen trouwe volgelingen weten wie hij is. Zijn vader, generaal Birabeau, krijgt de opdracht de Rode Schaduw onschadelijk te maken. Om verdenking te voorkomen doet hij thuis of hij een beetje achterlijk is. Niemand neemt hem daardoor aux seriaux.
Hij is verlieifd op de nicht van zijn vader, "Margot Bonvalet". Margot is verloofd met kapitein Paul Fontaine. Fontaine heeft een verhouding gehad met een halfbloed Azuri, die gevaarlijk wordt wanneer Paul een einde aan zijn liefdesbetrekkingen met haar heeft gemaakt.
Zij ontdekt wie de Rode Schaduw is. Margot komt in aanraking met de Rode Schaduw en wordt verliefd op hem. Hij schaakt haar. Zij wordt naar het harem van Ali-Ben-Ali, een Arabische vriend van de Rode Schaduw, gebracht. Zijn vader, opgestookt door Azuri, wil met hem duelleren. Hij weigert en wordt door Ali-Ben-Ali de woestijn ingestuurd.
Een stomdronken Azuri kan haar geheim niet langer voor zich houden en vertelt generaal Beirabeu de waarheid omtrent zijn zoon. De humor bregen Bennie Kidd en Susan, zijn secretaresse. Zij hebben de wonderlijkste avonturen. Dat Pierre met Margot Bonvalet gaat trouwen zal iedereen nu begrijpen. En verder... moet er iets te raden overblijven.