How do human brain networks react to dynamic changes in the sensory environment? We measured rapid changes in brain network organization in response to brief, discrete, salient auditory stimuli. We estimated network topology and distance parameters in the immediate central response period, <1 s following auditory presentation of standard tones interspersed with occasional deviant tones in a mismatch-negativity (MMN) paradigm, using magnetoencephalography (MEG) to measure synchronization of high-frequency (gamma band; 33-64 Hz) oscillations in healthy volunteers. We found that global small-world parameters of the networks were conserved between the standard and deviant stimuli. However, surprising or unexpected auditory changes were associated with local changes in clustering of connections between temporal and frontal cortical areas and with increased interlobar, long-distance synchronization during the 120- to 250-ms epoch (coinciding with the MMN-evoked response). Network analysis of human MEG data can resolve fast local topological reconfiguration and more long-range synchronization of high-frequency networks as a systems-level representation of the brain's immediate response to salient stimuli in the dynamically changing sensory environment.