We report the discovery of PSR J1101-6101, a 62.8 ms pulsar in IGR J11014-6103, a hard X-ray source with a jet and a cometary tail that strongly suggests it is moving away from the center of the supernova remnant (SNR) MSH 11-61A at v>1000 km/s. Two XMM-Newton observations were obtained with the EPIC pn in small window mode, resulting in the measurement of its spin-down luminosity E_dot = 1.36e36 erg/s, characteristic age Tau_c = 116 kyr, and surface magnetic field strength B_s = 7.4e11 G. In comparison to Tau_c, the 10-30 kyr age estimated for MSH 11-61A suggests that the pulsar was born in the SNR with initial period in the range 54