This paper proposes a distributed Reed-Solomon coded cooperative labeling diversity (DRSCC-LD) scheme over the Rayleigh frequency-flat fast fading channel to further improve the BER performance. The non-binary Reed-Solomon (RS) code with more consecutive roots is applied at the relay to provide additional redundancy. As a novel diversity technique, labeling diversity (LD) with three different mappers is employed in the proposed DRSCC-LD scheme utilizing 16-QAM and 64-QAM, respectively, which may achieve diversity gain and greatly decrease the error floor (EF). Besides, a reduced-complexity detection algorithm based on a variable signal subset (RC-VSS) is proposed to lower the complexity of detection at both relay and destination. The proposed critical SNR-assisted (CSA) joint decoding algorithm then collaborates with the joint detection based on the RC-VSS algorithm to improve the overall BER performance. Theoretical analysis and Monte Carlo simulated results reveal that the proposed DRSCC-LD scheme clearly outperforms its corresponding non-cooperative RS coded scheme by a gain of more than 7 dB and the existing schemes by a margin of more than 3.5 dB under the identical conditions, respectively.