Graph models of the brain hold great promise as a framework to study functional and structural brain connectivity across scales and species. The network-based statistic (NBS) is a well-known tool for performing statistical inference on brain graphs, which controls the family-wise error rate in a mass univariate analysis by combining the cluster-based permutation technique and the graph-theoretical concept of connected components. As the NBS is based on group-level inference statistics, it does not inherently enable informed decisions at the level of individuals, which is, however, necessary for the realm of precision medicine. Here we introduce NBS-Predict, a new approach that combines the powerful features of machine learning (ML) and the NBS in a user-friendly graphical user interface (GUI). By combining ML models with connected components in a cross-validation (CV) structure, the new methodology provides a fast and convenient tool to identify generalizable neuroimaging-based biomarkers. The purpose of this paper is to (i) introduce NBS-Predict and evaluate its performance using two sets of simulated data with known ground truths, (ii) demonstrate the application of NBS-Predict in a real case-control study, including resting-state functional magnetic resonance imaging (rs-fMRI) data acquired from patients with schizophrenia, (iii) evaluate NBS-Predict using rs-fMRI data from the Human Connectome Project 1200 subjects release. We found that: (i) NBS-Predict achieved good statistical power on two sets of simulated data; (ii) NBS-Predict classified schizophrenia with an accuracy of 90% using subjects’ functional connectivity matrices and identified a subnetwork with reduced connections in the group with schizophrenia, mainly comprising brain regions localized in frontotemporal, visual, and motor areas, as well as in the subcortex; (iii) NBS-Predict also predicted general intelligence scores from resting-state fMRI connectivity matrices with a prediction score of r = 0.2 and identified a large-scale subnetwork associated with general intelligence. Overall results showed that NBS-Predict performed comparable to or better than pre-existing feature selection algorithms (lasso, elastic net, top 5%, p-value thresholding) and connectome-based predictive modeling (CPM) in terms of identifying relevant features and prediction accuracy.