The roll-up and pairing of a two-dimensional temporally evolving non-Newtonian mixing layer have been simulated numerically using two rheological models: the Oldroyd-B and FENE-P models. Simulations with the Oldroyd-B model were limited to moderate Weissenberg numbers due to instabilities that are related to the nature of the model which allows the polymer to extend indefinitely and therefore causes the normal stresses to grow rapidly. This happens whenever the product of the Weissenberg number and the dimensionless local extensional rate exceeds unity. Results from the FENE-P model showed that the global vortex structure as well as the roll-up and pairing times are not affected by viscoelasticity over the range of parameters studied. However, the vorticity distribution is changed with high intensification occurring in the braids as well as in some regions of the core. This intensification is identified with the build-up of high polymer first normal stresses. The examination of the evolution of the first normal stresses revealed that the stresses are initially entrained by the roll-up of the flow and then reach a steady state characterized by the absence of any extensional forces and a balance between shearing forces and the polymer relaxation stresses. In the case of the pairing, the global development of the flow does not show important changes from the Newtonian case. However, the presence of viscoelasticity leads to a faster rotational motion of the two parent vortices around each other. In agreement with experimental results, we observed a trend for smaller values of the minimal vorticity in the case of the viscoelastic flow as well as the tendency for the vortex structures to be more compact and to have longer life times than in the Newtonian fluid.