Background: A procedure to measure connectedness among herds was applied to a beef cattle population bred by natural service. It consists of two steps: (a) computing coefficients of determination (CDs) of comparisons among herds; and (b) building sets of connected herds. Methods. The CDs of comparisons among herds were calculated using a sampling-based method that estimates empirical variances of true and predicted breeding values from a simulated n-sample. Once the CD matrix was estimated, a clustering method that can handle a large number of comparisons was applied to build compact clusters of connected herds of the Bruna dels Pirineus beef cattle. Since in this breed, natural service is predominant and there are almost no links with reference sires, to estimate CDs, an animal model was used taking into consideration all pedigree information and, especially, the connections with dams. A sensitivity analysis was performed to contrast single-trait sire and animal model evaluations with different heritabilities, multiple-trait animal model evaluations with different degrees of genetic correlations and models with maternal effects. Results: Using a sire model, the percentage of connected herds was very low even for highly heritable traits whereas with an animal model, most of the herds of the breed were well connected and high CD values were obtained among them, especially for highly heritable traits (the mean of average CD per herd was 0.535 for a simulated heritability of 0.40). For the lowly heritable traits, the average CD increased from 0.310 in the single-trait evaluation to 0.319 and 0.354 in the multi-trait evaluation with moderate and high genetic correlations, respectively. In models with maternal effects, the average CD per herd for the direct effects was similar to that from single-trait evaluations. For the maternal effects, the average CD per herd increased if the maternal effects had a high genetic correlation with the direct effects, but the percentage of connected herds for maternal effects was very low, less than 12%. Conclusions: The degree of connectedness in a bovine population bred by natural service mating, such as Bruna del Pirineus beef cattle, measured as the CD of comparisons among herds, is high. It is possible to define a pool of animals for which estimated breeding values can be compared after an across-herds genetic evaluation, especially for highly heritable traits. © 2010 Tarrés et al; licensee BioMed Central Ltd.