Resting-state fMRI studies have gained widespread use in exploratory studies of neuropsychiatric disorders. Graph metrics derived from whole brain functional connectivity studies have been used to reveal disease-related variations in many neuropsychiatric disorders including major depression (MDD). These techniques show promise in developing diagnostics for these often difficult to identify disorders. However, the analysis of resting-state datasets is increasingly beset by a myriad of approaches and methods, each with underlying assumptions. Choosing the most appropriate preprocessing parameters a priori is difficult. Nevertheless, the specific methodological choice influences graph-theoretical network topologies as well as regional metrics. The aim of this study was to systematically compare different preprocessing strategies by evaluating their influence on group differences between healthy participants (HC) and depressive patients. We thus investigated the effects of common preprocessing variants, including global mean-signal regression (GMR), temporal filtering, detrending, and network sparsity on group differences between brain networks of HC and MDD patients measured by global and nodal graph theoretical metrics. Occurrence of group differences in global metrics was absent in the majority of tested preprocessing variants, but in local graph metrics it is sparse, variable, and highly dependent on the combination of preprocessing variant and sparsity threshold. Sparsity thresholds between 16 and 22% were shown to have the greatest potential to reveal differences between HC and MDD patients in global and local network metrics. Our study offers an overview of consequences of methodological decisions and which neurobiological characteristics of MDD they implicate, adding further caution to this rapidly growing field. Hum Brain Mapp 37:1422-1442, 2016. © 2016 Wiley Periodicals, Inc.