We investigate the ultrafast spin dynamics in an epitaxial hcp(1100) cobalt thin film. By performing pump-probe magneto-optical measurements with the magnetization along either the easy or hard magnetic axis, we determine the demagnetization and recovery times for the two axes. We observe a 35% slower dynamics along the easy magnetization axis, which we attribute to magneto-crystalline anisotropy of the electron-phonon coupling, supported by our ab initio calculations. This points towards an unambiguous and previously undisclosed role of anisotropic electron-lattice coupling in ultrafast magnetism.