We present a method to estimate preferences in the presence of unobserved choice set heterogeneity. We build on the insights of Chamberlain's Fixed-Effect Logit and exploit information in observed purchase decisions in either panel or cross-section environments to construct "sufficient sets" of choices that lie within consumers' true but unobserved choice sets. This allows us to recover preference parameters without having to specify the process of choice set formation. We illustrate our ideas by estimating demand for chocolate bars on-the-go using individual-level data from the UK. Our results show that failing to account for unobserved choice set heterogeneity can lead to statistically and economically significant biases in the estimation of preference parameters.