The linear stability analysis of plane Poiseuille flow in a Maxwell fluid in the presence of a uniform cross-flow is studied. The physical problem is reduced to a modified Orr-Sommerfeld equation with nonlinear eigenvalues and solved numerically using the Chebyshev spectral collocation method. Attention is focused on the combined effects of uniform cross-flow and the relaxation time of the fluid (Deborah number) on the flow stability. Results obtained in this framework show that, the cross-flow can either delay or advances the instability of this system, respectively for the case of a Newtonian fluid and for the case of a Maxwell one. In addition, the system is apt to lose its instability with the fluid's elasticity in short wavelength and to enhance this instability in the long wavelength regime.