Accessing, organizing, and manipulating home videos present technical challenges due to their unrestricted content and lack of storyline. In this paper, we present a methodology to discover cluster structure in home videos, which uses video shots as the unit of organization, and is based on two concepts: (i) the development of statistical models of visual similarity and temporal duration and adjacency of consumer video segments, and (ii) the reformulation of hierarchical clustering as a sequential binary Bayesian classification process. A Bayesian formulation allows for the incorporation of prior knowledge of the structure of home video, and offers the advantages of a principled methodology. Gaussian mixture models are used to represent the class-conditional distributions of inter-segment visual similarity, and temporal adjacency and duration. The models are then used in the probabilistic clustering algorithm, where the merging order is a variation of Highest Confidence First, and the merging criterion is Maximum a Posteriori. The algorithm does not need any ad-hoc parameter determination. We present extensive results on a ten-hour home video database with ground-truth which thoroughly validate the performance of our methodology with respect to cluster detection, individual shot-cluster labeling, and the effect of prior selection.