Multi-wavelength observations show that Abell 1367 (A1367) is a dynamically young cluster, with at least two subclusters merging along the SE-NW direction. With the wide-field XMM-Newton mosaic of A1367, we discover a previously unknown merger shock at the NW edge of the cluster. We estimate the shock Mach number from the density and temperature jumps as $M_{rho}=1.21pm0.08$ and $M_T=1.60pm0.07$, respectively. This shock region also corresponds to a radio relic discovered with the VLA and GBT, which could be produced by the shock re-acceleration of pre-existing seed relativistic electrons. We suggest that some of the seed relativistic electrons originate from late-type, star-forming galaxies in this region.