Superelasticity associated with the martensitic transformation has found a broad range of engineering applications1,2. However, the intrinsic hysteresis3 and temperature sensitivity4 of the first-order phase transformation significantly hinder the usage of smart metallic components in many critical areas. Here, we report a large superelasticity up to 15.2% strain in [001]-oriented NiCoFeGa single crystals, exhibiting non-hysteretic mechanical responses, a small temperature dependence and high-energy-storage capability and cyclic stability over a wide temperature and composition range. In situ synchrotron X-ray diffraction measurements show that the superelasticity is correlated with a stress-induced continuous variation of lattice parameter accompanied by structural fluctuation. Neutron diffraction and electron microscopy observations reveal an unprecedented microstructure consisting of atomic-level entanglement of ordered and disordered crystal structures, which can be manipulated to tune the superelasticity. The discovery of the large elasticity related to the entangled structure paves the way for exploiting elastic strain engineering and development of related functional materials.