To evaluate the feasibility and performance of compressed sensing (CS) with magnitude subtraction regularization in accelerating non-contrast-enhanced dynamic intracranial MR angiography (NCE-dMRA). A CS algorithm was introduced in NCE-dMRA by exploiting the sparsity of the magnitude difference of the control and label images. The NCE-dMRA data were acquired using golden-angle stack-of-stars trajectory on six healthy volunteers and one patient with arteriovenous fistula. Images were reconstructed using (i) the proposed magnitude-subtraction CS (MS-CS); (ii) complex-subtraction CS; (iii) independent CS; and (iv) view-sharing with k-space weighted image contrast (KWIC). The dMRA image quality was compared across the four reconstruction strategies. The proposed MS-CS method was further compared with KWIC for temporal fidelity of depicting dynamic flow. The proposed MS-CS method was able to reconstruct NCE-dMRA images with detailed vascular structures and clean background. It provided better subjective image quality than the other two CS strategies (P < 0.05). Compared with KWIC, MS-CS showed similar image quality, but reduced temporal blurring in delineating the fine distal arteries. The MS-CS method is a promising CS technique for accelerating NCE-dMRA acquisition without compromising image quality and temporal fidelity. Magn Reson Med 79:867-878, 2018. © 2017 International Society for Magnetic Resonance in Medicine.