The prediction of cancer staging in prostate cancer is a process for estimating the likelihood that the cancer has spread before treatment is given to the patient. Although important for determining the most suitable treatment and optimal management strategy for patients, staging continues to present significant challenges to clinicians. Clinical test results such as the pre-treatment Prostate-Specific Antigen (PSA) level, the biopsy most common tumor pattern (Primary Gleason pattern) and the second most common tumor pattern (Secondary Gleason pattern) in tissue biopsies, and the clinical T stage can be used by clinicians to predict the pathological stage of cancer. However, not every patient will return abnormal results in all tests. This significantly influences the capacity to effectively predict the stage of prostate cancer. Herein we have developed a neuro-fuzzy computational intelligence model for classifying and predicting the likelihood of a patient having Organ-Confined Disease (OCD) or Extra-Prostatic Disease (ED) using a prostate cancer patient dataset obtained from The Cancer Genome Atlas (TCGA) Research Network. The system input consisted of the following variables: Primary and Secondary Gleason biopsy patterns, PSA levels, age at diagnosis, and clinical T stage. The performance of the neuro-fuzzy system was compared to other computational intelligence based approaches, namely the Artificial Neural Network, Fuzzy C-Means, Support Vector Machine, the Naive Bayes classifiers, and also the AJCC pTNM Staging Nomogram which is commonly used by clinicians. A comparison of the optimal Receiver Operating Characteristic (ROC) points that were identified using these approaches, revealed that the neuro-fuzzy system, at its optimal point, returns the largest Area Under the ROC Curve (AUC), with a low number of false positives (FPR = 0.274, TPR = 0.789, AUC = 0.812). The proposed approach is also an improvement over the AJCC pTNM Staging Nomogram (FPR = 0.032, TPR = 0.197, AUC = 0.582).