Intra-genotypic variability (IGV) occurs when individuals with the same genotype, raised in the same environment and then tested under the same conditions, express different trait values. Game theoretical and bet-hedging models have suggested two ways that a single genotype might generate variable behaviour when behavioural variation is discrete rather than continuous: behavioural polyphenism (a genotype produces different types of individuals, each of which consistently expresses a different type of behaviour) or stochastic variability (a genotype produces one type of individual who randomly expresses different types of behaviour over time). We first demonstrated significant differences across 14 natural genotypes of male Drosophila melanogaster in the variability (as measured by entropy) of their microhabitat choice, in an experiment in which each fly was allowed free access to four different types of habitat. We then tested four hypotheses about ways that within-individual variability might contribute to differences across genotypes in the variability of microhabitat choice. There was no empirical support for three hypotheses (behavioural polymorphism, consistent choice, or time-based choice), nor could our results be attributed to genotypic differences in activity levels. The stochastic variability hypothesis accurately predicted the slope and the intercept of the relationship across genotypes between entropy at the individual level and entropy at the genotype level. However, our initial version of the stochastic model slightly but significantly overestimated the values of individual entropy for each genotype, pointing to specific assumptions of this model that might need to be adjusted in future studies of the IGV of microhabitat choice. This is among a handful of recent studies to document genotypic differences in behavioural IGV, and the first to explore ways that genotypic differences in within-individual variability might contribute to differences among genotypes in the predictability of their behaviour.