Stretching driven polydomain-monodomain (PM) transitions have been investigated for the two types of polydomain nematic elastomers with different random alignments of the mesogens in the stage of cross-linking. One (I-PNE) is made by cross-linking in the high-temperature isotropic state and then cooling to the nematic state. The other (N-PNE) is directly obtained by cross-linking in the low-temperature polydomain nematic state. They are similar in the order of the induced monodomain as well as the phase transition temperature, but they markedly differ in the process of the PM transitions. The transition in I-PNEs occurs under a very small constant-force condition, and the work of deformation required for forming the monodomain state (W-PM) is only a few percent of the initial shear modulus. In contrast, the transition of N-PNEs requires a significantly larger W-PM, and the formation proceeds gradually in the wide range of stress. The optical microscopy observation reveals that N-PNEs possess the memory of the initial polydomain texture before cross-linking. The broad PM transition in N-PNEs stems from the memory effect of randomness which results in a robust constraint to the reorientation of local directors.