Abstract: A backfilling body-coal pillar-backfilling body (BPB) structure formed by pillar-side cemented paste backfilling can bear overburden stress and ensure safe mining. However, the failure response of BPB composite samples must be investigated. This paper examines the deformation characteristics and damage evolution of six types of BPB composite samples using a digital speckle correlation method under uniaxial compression conditions. A new damage evolution equation was established on the basis of the input strain energy and dissipated strain energy at the peak stress. The prevention and control mechanisms of the backfilling body on the coal pillar instability were discussed. The results show that the deformation localization and macroscopic cracks of the BPB composite samples first appeared at the coal–backfilling interface, and then expanded to the backfilling elements, ultimately appearing in the coal elements. The elastic strain energy in the BPB composite samples reached a maximum at the peak stress, whereas the dissipated energy continued to accumulate and increase. The damage evolution curve and equation agree well with the test results, providing further understanding of instability prevention and the control mechanisms of the BPB composite samples. The restraining effect on the coal pillar was gradually reduced with decreasing backfilling body element’s volume ratio, and the BPB composite structure became more vulnerable to failure. This research is expected to guide the design, stability monitoring, instability prevention, and control of BPB structures in pillar-side cemented paste backfilling mining.