The EQ-5D-5L has recently been developed to improve the sensitivity of the widely used three-level version. Valuation studies are required before the use of this new instrument can be adopted. The use of discrete choice experiments (DCEs) in this area is a promising area of research. To test the plausibility and acceptability of estimating an Australian algorithm for the newly developed five-level version of the EQ-5D using a DCE. A choice experiment was designed, consisting of 200 choice sets blocked such that each respondent answered 10 choice sets. Each choice set presented two health state-duration combinations, and an immediate death option. The experiment was implemented in an online Australian-representative sample. A random-effects probit model was estimated. To explore the feasibility of the approach, an indicative algorithm was developed. The algorithm is transformed to a 0 to 1 scale suitable for use to estimate quality-adjusted life-year weights for use in economic evaluation. A total of 973 respondents undertook the choice experiment. Respondents were slightly younger and better educated than the general Australian population. Of the 973 respondents, 932 (95.8 %) completed all ten choice sets, and a further 12 completed some of the choice sets. In choice sets in which one health state-duration combination dominated another, the dominant option was selected on 89.5 % of occasions. The mean and median completion times were 17.9 and 9.4 min, respectively, exhibiting a highly skewed distribution. The estimation results are broadly consistent with the monotonic nature of the EQ-5D-5L. Utility is increasing in life expectancy (i.e., respondents tend to prefer health profiles with longer life expectancy), and mainly decreases in higher levels in each dimension of the instrument. A high proportion of respondents found the task clear and relatively easy to complete. DCEs are a feasible approach to the estimation of utility weights for more complex multi-attribute utility instruments such as the EQ-5D-5L.