Small-angle X-ray scattering (SAXS) and elastic measurements were made for polyelectrolyte gel-surfactant complexes (PSCg) of polyacrylate-dodecylpyridinium (PAA-DP) and polyacrylate-cetylpyridinium (PAA-CP) at various NaCl concentrations (C-s). Sharp peaks in the SAXS spectra were observed at C-s lower than 200 mM and disappeared at C-s above 200 mM, where a single broad peak emerged. The sharp peaks of PAA-DP and PAA-CP, respectively, are assigned to the Pm3n cubic and the hexagonal structures, while the single broad peak is due to the correlated pair distribution function of micelles in the liquidlike state. In uniaxially stretching the PSCg, an abnormally large relaxation elastic modulus, of several 10(5) Pa, was observed at C-s below about 200 mM, while a relaxation elastic modulus smaller than 10(3) Pa was observed at C-s above 200 mM. The transitional changes of the steady moduli of the PSCg were also observed at C-s around 200 mM. The relaxation elastic modulus of the PSCg changed transitionally from 200 to 25 kPa with temperature rising from 34 to 36 degreesC. The results described above clearly demonstrate the existence of an order-disorder or a solid-liquidlike phase transition of the PSCg.