Transits in the planetary system WASP-4 were recently found to occur 80s earlier than expected in observations from the TESS satellite. We present 22 new times of mid-transit that confirm the existence of transit timing variations, and are well fitted by a quadratic ephemeris with period decay dP/dt = -9.2 +/- 1.1 ms/yr. We rule out instrumental issues, stellar activity and the Applegate mechanism as possible causes. The light-time effect is also not favoured due to the non-detection of changes in the systemic velocity. Orbital decay and apsidal precession are plausible but unproven. WASP-4b is only the third hot Jupiter known to show transit timing variations to high confidence. We discuss a variety of observations of this and other planetary systems that would be useful in improving our understanding of WASP-4 in particular and orbital decay in general.