"She" (original title: "She: A History of Adventure") is a classic pulp fantasy novel written by H. Rider Haggard all the way back in 1887. If I remember correctly, Queen Ayesha, known to her subjects as "She-Who-Must-Be-Obeyed, was an immortal jungle sorceress who menaces and eventually falls in love with Leo Vincey, our stalwart hero. In the end, she tries to make him immortal, too, but her spell, which involves walking through a pillar of fire in a volcano, doesn't work out right, and she dies as an immeasurably old woman. The story was followed by two sequels: 1905's "Ayesha" and "Wisdom's Daughter" in 1923.

Thanks to Master Villain for additional info. He's lucky enough to have access to a first edition of the book!