Cemented paste backfill (CPB) technology is widely used for environmental protection and underground goaf treatment. The influences of solid concentration, coarse aggregates dosage, and cement dosage on the rheological properties and compressive strength of CPB blended with coarse aggregates (CA-CPB) are investigated through three-factor and four-level orthogonal experiments. The dynamic shear stress and plastic viscosity are selected to characterize the rheological properties of CA-CPB. The uniaxial compressive strength (UCS) is used to describe the compressive strength. The effect of each factor on rheological properties is different from that on UCS. The most significant influences on rheological properties and UCS are solid concentration and cement dosage, respectively. The optimal levels of each factor for rheological properties and UCS are different, resulting in different optimal combinations obtained through range analysis. Therefore, the overall desirability function approach is employed to perform multiple response optimization. The optimal parameters for high fluidity and strength obtained provide valuable information for the CA-CPB process in the Chifeng Baiyinnuoer Lead and Zinc Mine.