The recycling of construction waste composite powder materials (CWCPM) conserves resources and protects the environment. To study the effect of CWCPM as a supplementary cementitious material (SCM) on concrete performance, the mechanical properties, permeability and pore structure characteristics of concrete with CWCPM were investigated at different water-cement ratios, CWCPM mixing amounts and curing ages. The pore axis fractal dimension Df was used to characterize the pore structure, and the inherent correlations among the compressive strength, permeability and pore structure were analyzed. Furthermore, the improvement mechanism of the CWCPM on concrete performance was revealed by scanning electron microscopy (SEM) and energy dispersive spectrometry (EDS) analyses. The results show that the incorporation of CWCPM enriched the quantity and types of hydration products and improve the pore structure, providing a complementary superposition effect on the cementitious material. The pore axis fractal dimension Df had a significant correlation with compressive strength and chloride ion permeability coefficients, and the correlation coefficients reached 0.936 and 0.901, respectively. The Df can characterize the pore structure of CWCPM-modified concrete. When the CWCPM mixing amount was 30%, the compressive strength and permeability of concrete were optimal.