Brain complexity, which reflects the ability of the brain to adapt to a changing environment, has been found to be significantly changed with age. However, there is less evidence on the alterations of brain complexity in neurodegenerative disorders such as Alzheimer’s disease (AD). Here we investigated the altered complexity of resting-state blood oxygen level-dependent signals in AD-related neurodegeneration using multiscale entropy (MSE) analysis. All participants were recruited from the Alzheimer’s Disease Neuroimaging Initiative, including healthy controls (HC, n=62), amnestic mild cognitive impairment (aMCI, n =81) patients, and Alzheimer’s disease (AD, n=25) patients. Our results showed time scale-dependent MSE differences across the three groups. In scale=1, significantly changed MSE patterns (HC>aMCI>AD) were found in four brain regions, including the hippocampus, middle frontal gyrus, intraparietal lobe, and superior frontal gyrus. In scale=4, reversed MSE patterns (HC<aMCI<AD) were found in the middle frontal gyrus and middle occipital gyrus. Furthermore, the values of regional entropy were significantly associated with cognitive functions positively on the short time scale, while negatively on the longer time scale. Our findings suggest that MSE could be a reliable measure for characterizing brain deterioration in AD, and may provide insights into the neural mechanism of AD-related neurodegeneration.