Major Depressive Disorder (MDD) is a very serious mental illness that can affect the daily lives of patients. Accurate diagnosis of this disorder is necessary for planning individualized treatment. However, diagnosing MDD requires the clinicians to personally interview the subjects and rate the symptoms based on Diagnostic and Statistical Manual of Mental Disorders (DSM), which can be very time consuming. Discovering quantifiable signals and biomarkers associated with MDD using functional magnetic resonance imaging (fMRI) scans of patients have the potential to assist the clinicians in their assessment. This paper explores the use of resting-state functional connectivity and network features to classify MDD vs. healthy subjects. For each subject, mean time-series are extracted from 85 brain regions and they are decomposed to 4-frequency bands. Mean time-series for each of the frequency bands are utilized to compute the Pearson correlation and network characteristics. Features are selected separately from correlation and network characteristics using Minimum Redundancy Maximum Relevance (mRMR) to create the final classifier. The proposed scheme achieves 79% accuracy (65 out of 82 subjects classified correctly) with 86% sensitivity (42 out of 49 MDD subjects identified correctly) and 70% specificity (23 out of 33 controls identified correctly) using leave-one-out classification with in-fold feature selection. Pearson correlation had the highest discrimination in band 0.015-0.03 Hz and network based features had the highest discrimination in band 0.03-0.06 Hz for distinguishing MDD vs. healthy subjects.