The incorporation of crumb rubber (CR) in concrete is associated with a negative effect on the mechanical properties of concrete due to the weak bond between CR and cement mortar. Consequently, there is a need to treat CR to improve its properties. This paper reports the effect of some CR treatment methods, such as NaOH, KMnO4, and cement coating in improving the mechanical properties of crumb rubber concrete (CRC). Up to 40% treated CR was used to replace fine aggregate in the preparation of CRC specimens. The effect of selected treatment methods on the surface texture and physical properties of CR was studied using Scanning Electron Microscopy and sedimentation measurements. The unit weight and compressive- and flexural-strength were measured to assess the mechanical properties of CRC. Further, statistical and cost analysis of the experimental data were carried out to identify the optimum treatment method. It was noted that the selected treatment methods cause crucial changes in the surface texture and shape of CR particles. The NaOH,- KMnO4,- and cement-treated CR exhibited a remarkable improvement in the sedimentation coefficient being 51.8%, 99.6% and 99.0%, respectively, compared to value of 37.2% for the untreated-CR. The NaOH- and KMnO4-treatment methods increased the compressive- and flexural-strength of CRC at low quantity of CR. But at higher quantities of CR, there was a degradation in the mechanical properties due to the agglomeration of CR particles. However, the agglomeration phenomenon was overcome by applying a cement coating that resulted in 64% and 33% increase in the compressive- and flexural-strength, respectively, in CRC with 40% replacement of CR with fine aggregate. The statistical analysis indicated that cement coating is the most effective treatment method as it significantly enhances the mechanical properties of CRC. In addition, there was a 22% decrease in the cost of CRC due to the cement-treatment of CR.