We introduce multi-attribute optimization under preference uncertainty, a novel approach for optimization-based decision support when the decision-maker’s preferences are uncertain. Here, each feasible design is associated with a vector of attributes, which is in turn assigned a utility by the decision-maker’s utility function. This utility function has been incompletely estimated, and its remaining uncertainty is quantified by a Bayesian probability distribution. We develop an optimization-based formulation to generate a menu of diverse solutions, among which the decision-maker is expected to find a high-utility solution. The resulting optimization problem is challenging to solve in general, but we show that it can be approximately solved efficiently when the attributes and utility function are linear by reformulating it as a mixed-integer linear program, and using sample average approximation and submodular maximization. We also propose a posterior sampling approach that only requires optimizing individual samples of the user’s utility function, supporting fast computation.