Recent evidence suggests brain-phenotype predictions may require very large sample sizes. However, as the sample size increases, missing data also increase. Conventional methods, like complete-case analysis, discard useful information and shrink the sample size. To address the missing data problem, we investigated rescuing these missing data through imputation. Imputation is substituting estimated values for missing data to be used in downstream analyses. We integrated imputation methods into the Connectome-based Predictive Modeling (CPM) framework. Utilizing four open-source datasets-the Human Connectome Project, the Philadelphia Neurodevelopmental Cohort, the UCLA Consortium for Neuropsychiatric Phenomics, and the Healthy Brain Network (HBN)-we validated and compared our framework with different imputation methods against complete-case analysis for both missing connectomes and missing phenotypic measures scenarios. Imputing connectomes exhibited superior prediction performance on real and simulated missing data compared to complete-case analysis. In addition, we found that imputation accuracy was a good indicator for choosing an imputation method for missing phenotypic measures but not informative for missing connectomes. In a real-world example predicting cognition using the HBN, we rescued 628 individuals through imputation, doubling the complete case sample size and increasing the variance explained by the predicted value by 45%. In conclusion, our study is a benchmark for state-of-the-art imputation techniques when dealing with missing connectome and phenotypic data in predictive modeling scenarios. Our results suggest that improving prediction performance can be achieved by strategically addressing missing data through effective imputation methods rather than resorting to the outright exclusion of participants. Our results suggest that rescuing data with imputation, instead of discarding participants with missing information, improves prediction performance.