Austin Powers is enjoying his honeymoon with his wife, the former Vanessa Kensington. She turns out to be one of Dr. Evil's fembots, who attempts to kill Austin, then self-destructs. Austin grieves briefly, then proceeds to the hotel lobby nude and celebrates being single again.
A NATO monitoring facility observes the return of Dr. Evil, confronting his son Scott, and then starting a riot, on The Jerry Springer Show, and informs British intelligence. At Dr. Evil's Seattle headquarters, Dr. Evil is presented with a one-eighth-size clone of himself whom he calls Mini-Me.
Dr. Evil unveils his latest evil plan: he has developed a time machine to go back to the 1960s and steal Austin's mojo, the source of Austin's sexual appeal. Dr. Evil and Mini-Me go back to 1969 and meet a younger Number Two and Frau Farbissina. An obese "Scottish Guard" called Fat Bastard extracts Austin's mojo from his frozen body at the Ministry of Defence Cryo Chamber. British intelligence warns Austin that one of Dr. Evil's agents is after him, and during a photo shoot the wanton Ivana Humpalot seduces him, but at the last moment she claims he is too sexy for her to kill him. They have sex in his bed, but do not get far before he discovers that he has lost his mojo and is impotent.
The MOD sends Austin back to 1969 with its own time travel device, a convertible Volkswagen New Beetle. Austin arrives at a party in his London pad and with the assistance of a CIA agent, Felicity Shagwell, escapes an assassination attempt by two of Dr. Evil's operatives. Austin and Felicity are pursued by Mustafa, another of Dr. Evil's henchmen; when caught he reveals the existence of Dr. Evil's secret volcano lair. Before he can divulge its location, Mini-Me shoots him in the neck with a dart, causing him to fall off a cliff.
After examining photographs from the crime scene at MOD headquarters, Austin identifies Fat Bastard as the perpetrator of the theft of his mojo. At Dr. Evil's lair, Fat Bastard arrives with Austin's mojo. Dr. Evil drinks some of it and has sex with Frau Farbissina. This results in an awkward situation when Frau reveals that she is pregnant. At the same moment Scott, Dr. Evil's son, arrives through the time portal. Dr. Evil announces his latest planÂ â to hold the world ransom by threatening to destroy major cities each hour, using a giant laser on the Moon. In London, Austin and Felicity get to know each other, but when Felicity tries to have sex with Austin, he turns her down because of his lost mojo.
Under MOD instructions to implant a homing device into Fat Bastard, Felicity seduces him, allowing her to plant it in his anus. Fat Bastard forces it out of his bowels into a Paddington Station toilet, but a stool sample from the scene is analyzed to reveal traces of a vegetable that only grows on one Caribbean island. Austin and Felicity arrive on the island, but are apprehended. They are put in a cell with a guard who is overcome when Felicity exposes her breasts. Dr. Evil and Mini-Me leave for the Moon to install the giant laser and are followed by Austin and Felicity, who hitch a ride on Apollo 11. In Dr. Evil's moon base, Austin battles with Mini-Me, eventually flushing him into space. As Austin confronts Dr. Evil, Dr. Evil gives him a choice: Save the world or Felicity, who is locked in a chamber with poison gas.
Felicity tells Austin to save the world and he succeeds in doing so by kicking Frau, diverting the laser and saving Washington D.C. Felicity is killed by the poison gas. Austin chases Dr. Evil and shoots him in the leg. Before Austin can kill him, Dr. Evil tells him he could use the time machine to save Felicity and the world. Austin travels ten minutes into the past, meeting up with himself and saving both the world and Felicity. Dr. Evil initiates the self-destruct mechanism of the moon base and escapes in his rocket after throwing Austin's mojo into the air. Both Austins fail to catch it and it crashes on the floor and is destroyed. Felicity points out that all the things Austin has done show that he never lost his mojo. They escape through the time portal to 1999.
At Austin's Pad, Fat Bastard makes another attempt to assassinate Austin, but Felicity disarms him. Felicity and Austin then throw a party. Dr. Evil recovers Mini-Me from space and vows to "get" Austin. On Jerry Springer, Scott learns he was not created in a test tube, but is the love child of Dr. Evil and Frau Farbissina. Austin returns to his pad, only to discover Felicity with the past Austin, who claims that since he and Austin are the same person, it is not cheating. Austin forgives Felicity.

Question: When does Austin first discover that his mojo has been stolen?
Answer: While trying to have sex with Ivana Humpalot.
Alternative answer: At Mod headquarters