Nanoparticles with an internal structure have been prepared by dispersing under dilute conditions poly(acrylic acid) with a polymerization degree n = 6000 (PAA6000) together with a cationic surfactant hexadecyltrimethylammonium hydroxide (C16TAOH) and the non-ionic surfactant penta(ethylene glycol) monododecyl ether (C12E5) in water. The nanoparticles are formed at different mixing ratios in the corresponding two-phase regions (liquid crystalline phase/dilute isotropic phase) of the C16TAPA6000 complex salt/C12E5/water ternary phase diagram. The particles consist of polyacrylate PA6000– polyions, C16TA+ surfactant ions, and C12E5. Their internal ordering was identified by small-angle X-ray scattering (SAXS) to be either bicontinuous cubic with the Ia3d crystallographic space group or normal hexagonal depending upon the amount of C12E5. The bicontinuous cubic phase, to our knowledge never observed before in polyelectrolyte–surfactant particle systems, was inferred by SAXS experiments. The data also showed that this structure is thermoresponsive in a reversible manner. The bicontinuous cubic space group transforms from Ia3d to Im3m as the temperature decreases from 25 to 15 °C. According to dynamic light scattering and electrophoretic mobility measurements, the particles have a well-defined size (apparent hydrodynamic radii RH in the range of 88–140 nm) and carry a positive net charge. The size of the nanoparticles is stable up to 1 month. The faceted nanoparticles are visualized by cryogenic transmission electron microscopy that also reveals their coexistence with thread-like C12E5 micelles.