The reliability of genomic prediction is influenced by several factors, including the size of the reference population, which makes genomic prediction for breeds with a relatively small population size challenging, such as Australian Red dairy cattle. Including other breeds in the reference population may help to increase the size of the reference population, but the reliability of genomic prediction is also influenced by the relatedness between the reference and validation population. Our objective was to optimize the reference population for genomic prediction of Australian Red dairy cattle. A reference population comprising up to 3,248 Holstein bulls, 48,386 Holstein cows, 807 Jersey bulls, 8,734 Jersey cows, and 3,041 Australian Red cows and a validation population with between 208 and 224 Australian Red Bulls were used, with records for milk, fat, and protein yield, somatic cell count, fertility, and survival. Three different analyses were implemented: single-trait genomic best linear unbiased predictor (GBLUP), multi-trait GBLUP, and single-trait Bayes R, using 2 different medium-density SNP panels: the standard 50K chip and a custom array of variants that were expected to be enriched for causative mutations. Various reference populations were constructed containing the Australian Red cows and all Holstein and Jersey bulls and cows, all Holstein and Jersey bulls, all Holstein bulls and cows, all Holstein bulls, and a subset of the Holstein individuals varying the relatedness between Holsteins and Australian Reds and the number of Holsteins. Varying the relatedness between reference and validation populations only led to small changes in reliability. Whereas adding a limited number of closely related Holsteins increased reliabilities compared with within-breed prediction, increasing the number of Holsteins decreased the reliability. The multi-trait GBLUP, which considered the same trait in different breeds as correlated traits, yielded higher reliabilities than the single-trait GBLUP. Bayes R yielded lower reliabilities than multi-trait GBLUP and outperformed single-trait GBLUP for larger reference populations. Our results show that increasing the size of a multi-breed reference population may result in a reference population dominated by one breed and reduce the reliability to predict in other breeds.