Structures built by animals may convey useful information about the builder that may be used by conspecifics in quality assessment. In fish, nest construction has been suggested to reflect qualities of individual builders, but little is known about how consistent individual differences are over time. If nest construction does reliably reflect builder quality, then we expect consistent variation between individuals in this extended phenotypic trait. We test this hypothesis in male three-spined sticklebacks, Gasterosteus aculeatus, by measuring the repeatability of nest characteristics. We encouraged males, caught from four populations in mid-Wales, U.K., to complete three consecutive nests under standardized laboratory conditions. We quantified a number of structural components and design characteristics of nests and estimated repeatability (r) of these traits. Within populations, the number of threads used, the area of the nest and the mass of substrate deposited on top of the nest were all repeatable within males (0.39 < r < 0.51), showing that individual male three-spined sticklebacks differed consistently in the size and composition of the nests they produced. Our data support the hypothesis that nest characteristics may reveal important information about the quality of individual males, and that they may, at least in part, be under genetic control. We discuss these findings in the context of the evolution of nest characteristics in sticklebacks and other species.