Currently, diagnosis for major depressive disorder (MDD) is largely reliant on self-reported symptoms. The ability to identify MDD without self-report is greatly needed. Implementing a graph-theoretical analysis on resting state fMRI (rsfMRI), we tested whether whole-brain network topology can be used as predictors of MDD using a machine learning algorithm. We found that MDD patients exhibit aberrant network centrality measures within the right hippocampus, supramarginal and parsopercularis. Using these as predictors in a machine learning algorithm we were able to classify MDD and controls with total accuracy of 81%, demonstrating the applicability of rsfMRI for diagnostics of MDD.