Mass loss near the ice-sheet margin is evident from remote sensing as frontal retreat and increases in ice velocities. Velocities in the ice sheet interior are orders of magnitude smaller, making it challenging to detect velocity change. Here, we analyze a 35-year record of remotely sensed velocities, and a 6-year record of repeated GPS observations, at the East Greenland Ice-core Project (EastGRIP), located in the middle of the Northeast-Greenland Ice Stream (NEGIS). We find that the shear margins of NEGIS are accelerating, indicating a widening of the ice stream. We demonstrate that the widening of the ice stream is unlikely to be a response to recent changes at the outlets of NEGIS. Modelling indicates that the observed spatial fingerprint of acceleration is more consistent with a softening of the shear margin, e.g. due to evolving fabric or temperature, than a response to external forcing at the surface or bed.