Nest construction by males is a common reproductive strategy in fishes, but little is known about intra-specific variation in nesting behavior and reproductive interactions with other species. In the southeastern USA, reproductive interactions between bluehead chub (Nocomis leptocephalus) and their nest associate, such as yellowfin shiner (Notropis lutipinnis), are mutualistic because the shiner requires chub nests to spawn but the chub also benefits from additional shiner eggs by reducing predation risk on their own eggs (i.e., dilution effect). As proxies for reproductive success of bluehead chub, we studied factors affecting their nest size variation and utilization by yellowfin shiner in three streams in the upper Piedmont region of South Carolina, USA. A total of 92 nests (71 spawned and 21 abandoned) were located, and we recorded spawning activity, nest size, number and size of male bluehead chub, number of yellowfin shiner, and environmental variables for 89 consecutive days in 2016. Path analysis showed that larger males spawned earlier in the season than smaller males, and instances of pebble re-use for nest construction increased through the spawning season, which extended from April to June. Larger males more likely shared the same nest with each other than smaller males, and larger or more males constructed larger nests and attracted more yellowfin shiner. Nest size also increased when males re-used substrate materials from old nests, and nests built in this manner (36 nests) were equally prevalent as newly constructed nests (35 nests). This study suggests that complex mechanisms mediate host nest size and interactions with nest associates, and individual variation likely shapes dynamics of the mutualistic reproductive interaction.