Characterizing the brain connectome using neuroimaging data and measures derived from graph theory emerged as a new approach that has been applied to brain maturation, cognitive function and neuropsychiatric disorders. For a broad application of this method especially for clinical populations and longitudinal studies, the reliability of this approach and its robustness to confounding factors need to be explored. Here we investigated test–retest reliability of graph metrics of functional networks derived from functional magnetic resonance imaging (fMRI) recorded in 33 healthy subjects during rest. We constructed undirected networks based on the Anatomic-Automatic-Labeling (AAL) atlas template and calculated several commonly used measures from the field of graph theory, focusing on the influence of different strategies for confound correction. For each subject, method and session we computed the following graph metrics: clustering coefficient, characteristic path length, local and global efficiency, assortativity, modularity, hierarchy and the small-worldness scalar. Reliability of each graph metric was assessed using the intraclass correlation coefficient (ICC). Overall ICCs ranged from low to high (0 to 0.763) depending on the method and metric. Methodologically, the use of a broader frequency band (0.008–0.15 Hz) yielded highest reliability indices (mean ICC = 0.484), followed by the use of global regression (mean ICC = 0.399). In general, the second order metrics (small-worldness, hierarchy, assortativity) studied here, tended to be more robust than first order metrics. In conclusion, our study provides methodological recommendations which allow the computation of sufficiently robust markers of network organization using graph metrics derived from fMRI data at rest.