Purpose: Different health state utility (HSU) instruments produce different utilities for the same individuals, thereby compromising the intended comparability of economic evaluations of health care interventions. When developing crosswalks, previous studies have indicated nonlinear relationships. This paper inquires into the degree of nonlinearity across the four most widely used HSU-instruments and proposes exchange rates that differ depending on the severity levels of the health state utility scale. Methods: Overall, 7933 respondents from six countries, 1760 in a non-diagnosed healthy group and 6173 in seven disease groups, reported their health states using four different instruments: EQ-5D-5L, SF-6D, HUI-3 and 15D. Quantile regressions investigate the degree of nonlinear relationships between these instruments. To compare the instruments across different disease severities, we split the health state utility scale into utility intervals with 0.2 successive decrements in utility starting from perfect health at 1.00. Exchange rates (ERs) are calculated as the mean utility difference between two utility intervals on one HSU-instrument divided by the difference in mean utility on another HSU-instrument. Results: Quantile regressions reveal significant nonlinear relationships across all four HSU-instruments. The degrees of nonlinearities differ, with a maximum degree of difference in the coefficients along the health state utility scale of 3.34 when SF-6D is regressed on EQ-5D. At the lower end of the health state utility scale, the exchange rate from SF-6D to EQ-5D is 2.11, whilst at the upper end it is 0.38. Conclusion: Comparisons at different utility levels illustrate the fallacy of using linear functions as crosswalks between HSU-instruments. The existence of nonlinear relationships between different HSU-instruments suggests that level-specific exchange rates should be used when converting a change in utility on the instrument used, onto a corresponding utility change had another instrument been used. Accounting for nonlinearities will increase the validity of the comparison for decision makers when faced with a choice between interventions whose calculations of QALY gains have been based on different HSU-instruments.