This paper presents the effect of desliming on the short- and long-term strength, stability and rheological properties of cemented paste backfill (CPB) produced from two different mill tailings. A 28-day unconfined compressive strength (UCS) of >= 1.0 MPa and the maintenance of stability over 224 days of curing were selected as the design criteria for the evaluation of paste backfill performance. Desliming induced some changes in the physical, chemical, mineralogical and rheological properties of the tailings. CPB mixture of the deslimed tailings achieved the required consistency at a lower water to cement ratio. The short-term UCSs of CPB samples of the deslimed tailings were found to be 30-100% higher than those samples of the reference tailings at all the binder dosages and curing times. CPB samples of the deslimed tailings achieved the long-term stability at relatively low binder dosages (e.g. 5 wt% c.f. >= 6.1% for the reference tailings). It was also estimated that desliming could allow a 13.4-23.1% reduction in the binder consumption depending apparently on the inherent characteristics of the tailings. Over the curing period, generation of sulphate and acid by the oxidation of pyrite present in the tailings was also monitored to correlate with the strength losses observed in the long term. Scanning electron microscope (SEM) and Mercury Intrusion Porosimetry (MIP) analyses provided an insight into the microstructure of CPB and the formation of secondary mineral phases (i.e. gypsum) confirming the beneficial effect of desliming. These findings suggest that desliming can be suitably exploited for CPB of sulphide-rich mill tailings to improve the strength and stability particularly in the long term and to reduce binder consumption. (C) 2012 Elsevier Ltd. All rights reserved.