Applying graph theoretical analysis of spontaneous BOLD fluctuations in functional magnetic resonance imaging (fMRI), we investigated whole-brain functional connectivity of 11 healthy volunteers during wakefulness and propofol-induced loss of consciousness (PI-LOC). After extraction of regional fMRI time series from 110 cortical and subcortical regions, we applied a maximum overlap discrete wavelet transformation and investigated changes in the brain's intrinsic spatiotemporal organization. During PI-LOC, we observed a breakdown of subcortico-cortical and corticocortical connectivity. Decrease of connectivity was pronounced in thalamocortical connections, whereas no changes were found for connectivity within primary sensory cortices. Graph theoretical analyses revealed significant changes in the degree distribution and local organization metrics of brain functional networks during PI-LOC: compared with a random network, normalized clustering was significantly increased, as was small-worldness. Furthermore we observed a profound decline in long-range connections and a reduction in whole-brain spatiotemporal integration, supporting a topological reconfiguration during PI-LOC. Our findings shed light on the functional significance of intrinsic brain activity as measured by spontaneous BOLD signal fluctuations and help to understand propofol-induced loss of consciousness.