Extension-induced crystallization in a heterogeneous polyethylene oxide (PEO) melt is investigated by small angle X-ray scattering (SAXS) and extensional rheology. The crystalline complex of PEO and sodium bromide is the heterogeneous component, which simulates the roles of crystal or strongly interacted additives during flow. It is aimed to demonstrate how the altered chain relaxation by the heterogeneous particle affects the crystallization. The main findings are listed as follows: (i) strain hardening occurs in heterogeneous melts but not in pure PEO. This indicates that the crystalline complex strengthens the entanglement network of free chains, leading to slower chain relaxation. (ii) In morphology, the orientation of lamellae becomes easier with the existence of the crystalline complex. A jump in the long period is also observed with large strain, accompanied by changes in the evolutional trend at the early stage. (iii) The crystallization kinetics converge with increasing strain; even the stress response significantly differs in different samples. Based on these findings, a quasi-network consisting of the crystalline complex and the entangled free chain is anticipated. Nucleation induced by the stretch of the quasi-network is supposed to lead to the change in crystallization observed.