The opera depicts fictional events in the life of the explorer Vasco da Gama.
Place: Lisbon, at sea, and in an exotic new land.Time: late 15th century
The council chamber, Lisbon
The beautiful Inèz is forced by her father, the Grand Admiral Don Diego, to marry Don Pédro instead of her true love, Vasco da Gama. Da Gama, who is thought to have died in the expedition of Bartolomeu Dias, appears at the Grand Council saying he has discovered a new land, and displaying Sélika and Nélusko as examples of a newly-discovered race. His request for an expedition is refused, causing da Gama to attack the Grand Inquisitor, who anathematises him. Da Gama is then imprisoned.
The prison
Sélika, who is in fact queen of the undiscovered land, saves da Gama, whom she loves, from being murdered by Nélusko, a member of her entourage. Inès agrees to marry Don Pédro if da Gama is freed; da Gama, not realising that Inès has made this bargain, and noticing her envy of Sélika, gives her Sélika and Nélusko as slaves. Don Pédro announces he is to mount an expedition to the new lands that were da Gama's discovery. Nélusko offers his services as pilot.
On Don Pedro's ship
Nélusko is navigating the ship, but is secretly planning to destroy the Europeans. He sings a ballad of the legend of Adamastor, the destructive giant of the sea. Nélusko gives orders which will direct the ship into an oncoming storm. Da Gama has followed Don Pédro in another ship, and begs him to change course to avoid destruction. Don Pédro refuses, and orders him to be chained. The storm breaks out. Nélusko leads the local people to kill all the Europeans on the ships and only da Gama is spared.
Sélika's island
Sélika is met with a grand celebration and swears to uphold the island's laws, which include the execution of all strangers. Da Gama is captured by priests, who intend to sacrifice him. He is amazed by the wonders of the island, and sings the most famous aria of the opera O Paradis! (O Paradise!). Sélika saves him by saying that he is her husband, forcing Nélusko to swear this is true. Da Gama resigns himself to this new life, but hearing the voice of Inès, who is being taken to her execution, he rushes to find her.
The island
The reunion of da Gama and Inès is interrupted by Sélika, who feels betrayed. When she realises the strength of the lovers' affection, she allows them to return to Europe, telling Nélusko to escort them to da Gama's boat. She then commits suicide by inhaling the perfume of the poisonous blossoms of the Manchineel tree. Nélusko follows her into death.