Captain EO and his crew, sent on a mission by "The Corps" and Commander Bog to deliver a gift to the Supreme Leader, first encounter her when they are captured by her minions. When she makes her entrance, she is a monstrous creature with a white face, long claws, a white and gray metallic jumpsuit, and is suspended from the ceiling by a series of wires.
Before she can punish the heroes (sentencing the captain to 100 years of torture in her deepest dungeon and turning his companions into trashcans), the captain presents her with his gift: the song "We Are Here to Change the World", which he performs with his crewmates to unlock the Supreme Leader's inner beauty and bring peace to her planet. He gains his power through the music, allowing him to transform the Leader's minions into human men and women, freeing her past prisoners, turning her planet into a more beautiful place and redeeming the Leader herself by changing her into a friendly and beautiful woman.
EO and his crew succeed and perform "Another Part of Me" as they bid the now-reformed Supreme Leader farewell and take off into the depths of space.