This research used waste ceramic powder (CP) to replace aggregate, fly ash (FA) as filler, and combined them with sulfur to prepare composite cementitious materials. The variations of the mechanical properties with the aggregate proportions (aggregate mass/total mass) of 65%, 70%, and 75%, and the FA contents (FA mass/aggregate and filler mass) of 0%, 10%, 20%, 30%, 40%, and 50% were studied. The correlation evaluation model of sulfur content, CP content, FA content, and mechanical properties was established using the gray correlation theory, and the comprehensive mechanical property evaluation model was established as the foundation of the entropy method. Finally, the optimum proportion of the solid-waste–sulfur-based cementitious composites was determined. Results showed that, without FA, the CP increased from 65% to 75% and the comprehensive mechanical properties of the specimen increased by 60.53%. After FA was added, the peak point of the comprehensive mechanical properties appeared in group S75F10, which was 0.9210. During the hardening of the cementitious material, sulfur was mainly used as a binder, CP played the role of skeleton and part of the filler, whereas, as a crystal nucleus, the FA promoted the transformation of the sulfur crystals. Both the CP and FA can reduce the porosity of the specimen to a certain extent and have potential defect repair ability, thus densifying the matrix and improving the strength. When the proportion of sulfur: CP: FA is 1:2.7:0.3, the flexural (FS), compressive (CS), and splitting tensile (STS) strengths of the specimen are 14.8, 86.2, and 6.8 MPa, respectively. The flexural (FCR) and tensile (TCR) compression ratios are 0.172 and 0.079, respectively.