Conventionally, generic quality-of-life health states, defined within multi-attribute utility instruments, have been valued using a Standard Gamble or a Time Trade-Off. Both are grounded in expected utility theory but impose strong assumptions about the form of the utility function. Preference elicitation tasks for both are complicated, limiting the number of health states that each respondent can value and, therefore, that can be valued overall. The usual approach has been to value a set of the possible health states and impute values for the remainder. Discrete Choice Experiments (DCEs) offer an attractive alternative, allowing investigation of more flexible specifications of the utility function and greater coverage of the response surface. We designed a DCE to obtain values for EQ-5D health states and implemented it in an Australia-representative online panel (n = 1,031). A range of specifications investigating non-linear preferences with respect to time and interactions between EQ-5D levels were estimated using a random-effects probit model. The results provide empirical support for a flexible utility function, including at least some two-factor interactions. We then constructed a preference index such that full health and death were valued at 1 and 0, respectively, to provide a DCE-based algorithm for Australian cost-utility analyses. Copyright © 2013 John Wiley & Sons, Ltd.