Controlling the strain level in nanowire heterostructures is critical for obtaining coherent interfaces of high crystalline quality and for the setting of functional properties such as photon emission, carrier mobility, or piezoelectricity. In a nanowire axial heterostructure featuring a sharp interface, strain is set by the materials lattice mismatch and the nanowire radius. Here we show that introducing a graded interface in nanowire heterostructures offers an additional parameter to control strain. For a given interface length and lattice mismatch, we first derive theoretically the maximum nanowire radius below which coherent growth is possible. We validate these findings by growing and characterizing various In(Ga)As/GaAs nanowire heterostructures with graded interfaces. We perform chemical and structural characterization of the interface by combining energy-dispersive x-ray spectroscopy and high resolution transmission electron microscopy. In the case of coherent growth, we observe that the mismatch strain relaxes elastically on the side walls of the nanowire around the interface area, while the core of the nanowire remains partially strained. Our experimental data show good agreement with finite element calculations. In particular, this analysis confirms that mechanical strain is largely reduced by interface grading. Overall, our work extends the parameter space for the design of nanowire heterostructures, thus opening new opportunities for nanowire optoelectronics. © 2020 American Physical Society.