Many extensions of the Standard Model predict the existence of axion-like particles (ALPs), which are very light spin-zero bosons with a two-photon coupling. We show that photon-ALP oscillations occurring in large-scale magnetic fields can produce harder photon spectra of very-high energy blazars. This effect is detecteble with the CTA and with the HAWC water Cherenkov gamma-ray observatory, and possibly with the currently operating Imaging Atmospheric Cherenkov Telescopes. Moreover, we show that the a new interpretation of the blazars detected so far above 100 GeV arises, according to which the large spread in the values of the observed spectral index is mainly due to the wide spread in the source distances rather than to large variations of their internal physical properties. We also show that the polarization pattern resulting from the current models of GRB emission can be drastically modified by the existence of ALPs. Searching for such a peculiar feature through future high- statistics polarimetric measurements therefore offers a new opportunity to discover ALPs.