That show's what happened at the end of the show, but where are these dudes during Beast Wars times etc?
Depends on which continuity you follow. The original Beast Wars premise was that Megatron and Optimus Primal where the original Megatron and Prime in new bodies set in the present day. But then the show happened and changed all that. As far as the story goes:
The Autobots eventually win the Great War and Decepticons surrender and sign the Pax Cybertronia. Earth is banished from the Transformers. No one is allowed to go there. An event happens (Energon shortage perhaps) which forces the Autobots and Decepticons to upgrades into smaller e energy efficient bodies which they begin to call themselves Maximals and Predacons. Optimus Prime faded into obscurity. That's just the broad scope of what happened. More importantly, the Maximals begin to treat the Predacons as second class citizens. This causes a Predacons who takes up the name Megatron to steal a transwarp drive and the golden discs which details the location of earth (which was a top guarded secret), details of the great war and a message from the original Megatron. A group of Maximals give chase, end up through a wormhole which lands them on prehistoric earth.
And that's just the American cartoon continuity. The Japanese goes further. It's hard to answer that question because while Takara and Hasbro have been working on the toys together since 1984, story wise? Transformers have a multiverse. For instance:
Dreamwave: They had Mircomasters (Hasbro way of competing with micro machines) be the prototypes for the Maximals and Predacons.
Japanese: G2 shows some ties to Beast Wars as the Mircomasters Metro Squad lands on earth and find the Maximal symbol on a set of doors by the Ark.