The environmental challenges associated with cement production and the increasing accumulation of construction and demolition waste have intensified the search for sustainable alternatives in concrete production. This study investigated the suitability of waste clay brick powder (WCBP) obtained from demolition wastes in Bayelsa State, Nigeria, as a partial replacement for Portland Cement (PC) in concrete. The objective was to evaluate the effects of WCBP on the workability and compressive strength of concrete while promoting waste utilization and reducing dependence on cement. Concrete specimens were produced by replacing PC with WCBP at replacement levels of 5%, 10%, 15%, and 20% by weight. Standard laboratory tests were conducted to determine the workability and compressive strength characteristics of the concrete mixes, and the results were compared with those of conventional concrete made with 100% PC. The findings showed that all WCBP-modified mixes exhibited satisfactory workability. The optimum performance was achieved at a 10% replacement level, where the 28-day compressive strength increased by approximately 14–15% compared with the control mix. Although higher replacement levels resulted in a gradual reduction in strength, the concrete remained suitable for selected non-structural applications. A one-way Analysis of Variance (ANOVA) was conducted to assess the statistical significance of the differences in compressive strength among the mixes. The analysis yielded an F-value of 1.526 and a p-value of 0.233. Since the p-value exceeded the 0.05 significance level, the differences among the mean compressive strengths were not statistically significant at the 95% confidence level. Nevertheless, the practical improvement observed at the 10% replacement level highlights the positive contribution of WCBP to concrete performance. The study concludes that replacing 10% of PC with WCBP provides the best balance between mechanical performance and environmental sustainability. The adoption of WCBP in concrete production can reduce cement consumption, lower carbon emissions, and provide an effective means of managing demolition waste. It is recommended that WCBP be considered as a supplementary cementitious material in sustainable construction, while further studies should investigate its long-term durability and field performance.