We report on the discovery of hard spectral tails for energies above 10 keV in the total and pulsed spectra of anomalous X-ray pulsars 1RXS J1708-4009, 4U 0142+61 and 1E 2259+586 using RXTE PCA (2-60 keV) and HEXTE (15-250 keV) data and INTEGRAL IBIS ISGRI (20-300 keV) data. Improved spectral information on 1E 1841-045 is presented. The pulsed and total spectra measured above 10 keV have power-law shapes and there is so far no significant evidence for spectral breaks or bends up to ~150 keV. The pulsed spectra are exceptionally hard with indices measured for 4 AXPs approximately in the range -1.0 -- 1.0. We also reanalyzed archival CGRO COMPTEL (0.75-30 MeV) data to search for signatures from our set of AXPs. No detections can be claimed, but the obtained upper-limits in the MeV band indicate that for 1RXS J1708-4009, 4U 0142+61 and 1E 1841-045 strong breaks must occur somewhere between 150 and 750 keV.