Large pure aluminum powders were deposited on as cast-, T4- and T6-AZ91D magnesium substrates using cold spray. Heat treatment was applied to the coated components under vacuum at 400°C for different holding time. The effects of the heat treatment on the microstructure as well as the coating/substrate adhesion strength were investigated. Thick (~ 400µm) and dense (<1% porosity) Al coatings have been obtained on the three different substrates. During heat treatment, Mg17Al12 (β) and Al3Mg2 (γ) intermetallic phases were formed at the Al/Mg interface and the thickness of the intermetallics layers increased with the holding time. No significant thickness difference of the intermetallics layers were observed on as cast- and T6-AZ91D substrates, while thicker layers took place on the T4- substrate. It is believed that the higher Al concentration within the T4-AZ91D material could be beneficial for intermetallic growth because less enrichment is required to reach the critical level for intermetallic formation in the substrate. Shear strength tests were performed on the as sprayed and after heat treatment coatings. The results revealed lower adhesion strength in the samples after heat treatment than the as sprayed ones which is attributed to the presence of brittle intermetallics layers at the coating/substrate interface.