We report the discovery of two new lithium-rich Cepheids in the Milky Way (A(Li)~2.9dex) among the targets of the MAGIC spectroscopic survey with the Southern African Large Telescope spectrographs. The 6707{AA} Li feature is usually not detectable in the atmosphere of Cepheids. Only three Cepheids (two in the Milky Way and one in the Large Magellanic Cloud) had been reported so far with high lithium abundances. We examine the possibility that the Li-rich Cepheids are evolving towards the red giant branch, crossing the instability strip for the first time, as well as other possible scenarios. The two stars are mixed-mode Cepheids pulsating simultaneously in the first and in the second overtone modes. We briefly discuss the possible connection between their unusual chemical composition and their pulsational properties.