Ce film est le premier long métrage de Karim Aïnouz, auteur de multiples courts, auparavant assistant à la réalisation et monteur.
Ce long métrage est inspiré d'un personnage qui a réellement existé : Joao Francisco dos Santos. Né en 1900 au Brésil peu de temps après l'abolition de l'esclavage, orphelin de père, vendu par sa mère contre une mule, noir, homosexuel, Joao Francisco dos Santos finit par s'installer dans le quartier marginal et interlope de Lapa à Rio. Entourée de prostituées et de proxénètes, il se produit en travesti dans des numéros de cabaret tout en élevant sept enfants et en changeant d'identité à de multiples reprises. Incarcéré plusieurs fois pour vols et meurtre, il n'en réussit pas moins à devenir populaire sous le nom de Madame Sata, inspiré du film Madame Satan de Cecil Blount de Mille. Dans les années 70, il devient un véritable mythe, égérie de l'underground et symbole de l'émergence au début du XXe siècle d'une culture afro-brésilienne urbaine.
Ce long métrage a été financé par la société de production VideoFilmes fondé en 1987 par Walter Salles et son frère Joao Moreira Salles. Le réalisateur de Madame Sata Karim Aïnouz avait collaboré au scénario d'Avril brisé de Walter Salles.
Ce film était en compétition officielle à Cannes en 2002 dans la section "Un Certain regard".
Madame Sata est une coproduction franco-brésilienne financée notamment par Studio Canal et soutenue par le Fonds Sud et la Procirep.