In western Canada, geophysical studies infer an abrupt change in crustal temperatures between the Canadian Cordillera and the adjacent North American craton, with important implications for the tectonics and geodynamics of the area. We use a wavelet analysis of magnetic anomaly data in western Canada to map the depth to the bottom of the magnetic source, or Curie depth. This depth corresponds to the point at which crustal rocks reach their Curie temperature, thus providing an estimate of geothermal gradient. Our model is defined by a fractal distribution of magnetization characterized by the parameter β, as well as the depths to the top (zt) and bottom (zb) of the magnetized layer. Synthetic tests reveal the increased accuracy of the estimated zb when values for zt and β are fixed prior to the inversion. We set zt to the thickness of sedimentary rocks overlying the magnetic bedrock and use various values of β to estimate zb. We determine β a posteriori by comparing Monte Carlo simulations of predicted heat flow values (assuming a Curie temperature of 580 °C) with observed heat flow in various regions. Our results suggest a β value of 2.5 for the Canadian Cordillera and Slave craton, and 2 for the remaining North American craton. The Curie depths resolve geological domains and important structural features, with estimates for zb averaging 15 ± 1 km in the Cordillera, 32 ± 3 km in the Slave craton, and 34 ± 3 km in the North American craton to the south.