This paper aims to explore the feasibility of neural architecture search (NAS) given only a pre-trained model without using any original training data. This is an important circumstance for privacy protection, bias avoidance, etc., in real-world scenarios. To achieve this, we start by synthesizing usable data through recovering the knowledge from a pre-trained deep neural network. Then we use the synthesized data and their predicted soft labels to guide NAS. We identify that the quality of the synthesized data will substantially affect the NAS results. Particularly, we find NAS requires the synthesized images to possess enough semantics, diversity, and a minimal domain gap from the natural images. To meet these requirements, we propose recursive label calibration to encode more relative semantics in images, as well as regional update strategy to enhance the diversity. Further, we use input and feature-level regularization to mimic the original data distribution in latent space and reduce the domain gap. We instantiate our proposed framework with three popular NAS algorithms: DARTS, ProxylessNAS and SPOS. Surprisingly, our results demonstrate that the architectures discovered by searching with our synthetic data achieve accuracy that is comparable to, or even higher than, architectures discovered by searching from the original ones, for the first time, deriving the conclusion that NAS can be done effectively with no need of access to the original or called natural data if the synthesis method is well designed. Code and models are available at: https://github.com/liuzechun/Data-Free-NAS. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.