Above the Planet Gaea, where Lio Convoy and his Maximals are fighting the Beast Wars against Galvatron and his Predacons, a strange ship appears. It disrupts a battle between the Jointrons and the Seacons, crash-landing on the planet.
The ship was created long ago by a race of technologically-advanced creatures. Within the ship is a device that can control space-time and pluck living creatures from any point in history. Needless to say, Galvatron wants it pretty bad. Lio Convoy sends Lio Junior to protect the ship from the Predacons until reinforcements can arrive. However, due to his inexperience, he is trounced by Hellscream and Max-B. The Predacons use the device to attempt to find "Megatron", however, Megastorm bungles the wavelength calculations and instead they summon forth Majin Zarak, a titanic battleship Transformer from the past who is virtually indestructible. Galvatron is delighted, taunting Lio Junior that "thanks to you, we obtained a weapon superior to Megatron".
Wanting to make amends and prove his maturity, Lio Junior combines with Santon and Skywarp, forming Magnaboss. He valiantly fights the Predacons away from the ship and uses the very last of his power and strength to summon an ally with the time-space machine.
On the battle field, the Maximals are getting trashed by the might of Majin Zarak. However, Majin Zarak eventually tires of Galvatron's orders and the incompetence of the Predacons. He tosses them out, proving to have a sentient intelligence he hadn't displayed before. Majin Zarak goes wild and all hope seems lost.
Then, suddenly, Optimus Primal appears. Everyone is surprised to see him, as the Maximals had thought Optimus Primal and his crew were dead. Primal and Lio Convoy team up and keep Majin Zarak occupied while the rest of the Maximals try to figure out his weakness. After a bit of research, they discover that the third eye on his forehead is where all his nerve-endings are clustered. The only way to defeat Majin Zarak is to strike there, and strike hard!
Optimus Primal and Lio Convoy use the power of their Energon Matrices to transform themselves into Flash Lio Convoy and Burning Convoy. They deliver a healthy bit of damage to Majin Zarak before unleashing the power of their Matrices and combine the energy into the "Double Matrix Blast". The powerful attack pierces Majin Zarak's eye, killing him on the spot.
The battle won, Lio Convoy and the Maximals ask Optimus Primal to stay with them. However, he declines as he wishes to continue fighting his own Beast Wars on prehistoric Earth. Optimus Primal returns home using the device on the space ship. After he leaves, the Maximals then destroy the machine so that it can never be used again.
It is unclear which "Megatron" Galvatron and his crew intended to summon across time and space: Generation One Megatron (who seems to better fit the given description of "the greatest and most vicious Transformer in history") or Beast Wars Megatron (who provides a better parallel to the appearance of Optimus Primal in the film)?
At the time the movie was released it was understood, per a Beast Wars II toy catalog which depicted Galvatron and Beast Wars Megatron as rivals, that the characters from Beast Wars and Beast Wars II hailed from the same "home" era despite their time-travel escapades. This, combined with the characters' antagonistic shared history, make it less likely that Beast Wars Megatron was the object of Galvatron's search.
The waters are significantly muddied by a retcon performed many years later by the Kiss Players timeline. This chronicle ignored the catalog and indicated that the Beast Wars II characters came from "tens of thousands of years" in the future, arguably (although likely) erasing Galvatron and Beast Wars Megatron's history together. In the retconned timeline, then, the above argument doesn't hold.
It doesn't help things that Japan occasionally 'forgot' that Beast Wars Megatron and Optimus Primal were separate characters from their Generation One counterparts, so that may also be a factor in the ambiguity. For example, in this very film the Beast Wars II Maximals venerate Optimus Primal as a "Legendary General Commander" despite his meager rank as a starship captain.