The anime I was looking for was Time Bokan. The real plot (from Wikipedia):
Dr. Kieta, a somewhat wacky but intelligent scientist, has finally
succeeded in inventing insect-shaped time machines called "Time
Bokan". To prove its efficiency and safety, he decides to serve as the
very first guinea pig for its maiden voyage. However, by the time his
machine has returned, there's no trace of him inside. The only thing
that it returns with is a talking parrot, along with a large gemstone
called the Dynamond (ダイナモンド, Dainamondo), which is seemingly the most
powerful and valuable jewel in the world.
Now it's up to a search party, founded by Dr. Kieta's lab assistant
Tanpei, to travel through time to find Dr. Kieta. However, it seems
that someone power hungry is looking for the "Dynamond" as well.[1]
The story starred two vividly opposing sides, the heroes, and the
villains. Typical plots follow this format:
The heroes travel to a particular era or space during their search for
Dr. Kieta, and their hunt for the nature of the Dynamond, meeting the
famous historical figures (and some times fictional characters) in the
process. The heroes eventually encounter the villains. The two sides
battle each other with their time machines. The villains always suffer
a crushing defeat, either due to the smart foiling of their plans from
the heroes, or due to the villains' own ineptitude.
In particular I was looking for a film called Time Fighters in the Land of Fantasy, that was made mostly of episodes themed around fairy tales.
