The Nemesis was a Decepticon warship under the control of Megatron. It showed up on the outskirts of Autobot-controlled space almost immediately after the legendary AllSpark was discovered by Optimus Prime and his crew of space bridge repair-bots. It attacked Teletran-1 in an attempt to capture the AllSpark. Megatron went out to attack them and seize the AllSpark personally, unaware his lieutenant, Starscream, had planted a circut-overloader on him. When the circut-overloader detonated, the Autobots' ship went out of control, plunging toward another space bridge portal. The AllSpark opened the space bridge and caused a shock wave in its wake, slagging the Nemesis and Starscream inside, while the other Decepticons escaped. For the next fifty stellar cycles, Starscream piloted the remains the ship, searching for the AllSpark to show the Decepticons he deserved to be their new leader. When its systems detected an AllSpark-like energy signature from a remote star system, he went to investigate. En route, he monitored television transmissions that depicted Prime and his Autobots as the new superheroes of Detroit.
After his escape from the Elite Guard ship, Starscream returned to the Nemesis and appeared to stay there for a full deca-cycle (10 days) until Prowl showed up to hunt for the Decepticon traitor to turn him in. Because of the intervention of Lockdown, Starscream eluded capture, and Prowl and Lockdown returned to Earth, unknowingly chasing after one of his clones. After the clone's failed attempt on Megatron's life, Starscream was again seen aboard the Nemesis, watching a transmission of Megatron telling the other Decepticons that the bounty on Starscream had increased. Enraged, Starscream swore vengence on Megatron, turning to show an entire hull full of Starscream clones.