To address the common industrial issues of loose gel networks, poor water-holding capacity, and unsuitable swallowing textures in low-salt chicken paste, this study utilized Qingyuan chicken breast as the matrix to systematically investigate the regulatory mechanisms of sodium carboxymethyl cellulose (CMC)-protein interactions at varying concentrations on the rheological behavior, microstructural phase transitions, and swallowing suitability of the low-salt chicken paste gel system. The results showed that CMC significantly reduced the cooking loss of low-salt chicken paste and improved their water-holding capacity. After CMC addition, the storage modulus and apparent viscosity generally decreased, indicating that the gel system became softer and more deformable. Texture results showed that CMC had a concentration-dependent effect on gel hardness and chewiness. The addition of 1%–2% CMC enhanced the gel structure, whereas the 3% CMC group showed the lowest hardness and chewiness, which were 41.51 g and 6.28, respectively. Microstructure and IDDSI results indicated that the 3% CMC group formed an obvious fibrous supporting network and was not easily dispersed after fork pressure, showing good bolus stability. FTIR results showed that an appropriate amount of CMC promoted the transformation of myofibrillar proteins from β-sheet structures to random coils, increasing the flexible conformation of proteins. In conclusion, 3% CMC effectively improved the softness, water-holding capacity, and swallowing suitability of low-salt chicken paste, providing a reference for the development of low-salt and easy-to-swallow chicken meat products.