Workability is a key performance criterion for mining cemented tailing backfill, which should be defined in terms of rheological parameters such as yield stress and plastic viscosity. Cemented tailing backfill is basically composed of mill tailings, Portland cement, or blended cement with supplementary cement material (fly ash and blast furnace slag) and water, among others, and it is important to characterize relationships between paste components and rheological properties to optimize the workability of cemented tailing backfill. This study proposes a combined model for predicting rheological parameters of cemented tailing backfill based on a principal component analysis (PCA) and a back-propagation (BP) neural network. By analyzing experimental data on mix proportions and rheological parameters of cemented tailing backfill to determine the nonlinear relationships between rheological parameters (i.e., yield stress and viscosity) and mix proportions (i.e., solid concentrations, the tailing/cement ratio, the specific weight, and the slump), the study constructs a prediction model. The advantages of the combined model were as follows: First, through the PCA, original multiple variables were represented by two principal components (PCs), thereby leading to a 50% decrease in input parameters in the BP neural network model, which covered 98.634% of the original data. Second, in comparison to conventional BP neural network models, the proposed model featured a simpler network architecture, a faster training speed, and more satisfactory prediction performance. According to the test results, any error between estimated and expected output values from the combined prediction model based on the PCA and the BP neural network was within 5%, reflecting a remarkable improvement over results for BP neural network models with no PCA.