We report the discovery of non-thermal pulsed X-ray/soft gamma-ray emission up to about 150 keV from the anomalous X-ray pulsar AXP 1E 1841-045 located near the centre of supernova remnant Kes 73 using RXTE PCA and HEXTE data. The morphology of the double-peaked pulse profile changes rapidly with energy from 2 keV up to about 8 keV, above which the pulse shape remains more or less stable. The pulsed spectrum is very hard, its shape above 10 keV can be described well by a power law with a photon index of 0.94 +/- 0.16. 1E 1841-045 is the first AXP for which such very-hard pulsed emission has been detected, which points to an origin in the magnetosphere of a magnetar.