Temperature and humidity levels above a certain threshold decrease milk production in dairy cattle, and genetic variation is associated with the amount of lost production. To enable selection for improved heat tolerance, the aim of this study was to develop genomic estimated breeding values (GEBV) for heat tolerance in dairy cattle. Heat tolerance was defined as the rate of decline in production under heat stress. We combined herd test-day recording data from 366,835 Holstein and 76,852 Jersey cows with daily temperature and humidity measurements from weather stations closest to the tested herds for test days between 2003 and 2013. We used daily mean values of temperature-humidity index averaged for the day of test and the 4 previous days as the measure of heat stress. Tolerance to heat stress was estimated for each cow using a random regression model with a common threshold of temperature-humidity index=60 for all cows. The slope solutions for cows from this model were used to define the daughter trait deviations of their sires. Genomic best linear unbiased prediction was used to calculate GEBV for heat tolerance for milk, fat, and protein yield. Two reference populations were used, the first consisted of genotyped sires only (2,300 Holstein and 575 Jersey sires), and the other included genotyped sires and cows (2,189 Holstein and 1,188 Jersey cows). The remainder of the genotyped sires were used as a validation set. All animals had genotypes for 632,003 single nucleotide polymorphisms. When using only genotyped sires in the reference set and only the first parity data, the accuracy of GEBV for heat tolerance in relation to changes in milk, fat, and protein yield were 0.48, 0.50, and 0.49 in the Holstein validation sires and 0.44, 0.61, and 0.53 in the Jersey validation sires, respectively. Some slight improvement in the accuracy of prediction was achieved when cows were included in the reference population for Holsteins. No clear improvements in the accuracy of genomic prediction were observed when data from the second and third parities were included. Correlations of GEBV for heat tolerance with Australian Breeding Values for other traits suggested heat tolerance had a favorable genetic correlation with fertility (0.29-0.39 in Holsteins and 0.15-0.27 in Jerseys), but unfavorable correlations for some production traits. Options to improve heat tolerance with genomic selection in Australian dairy cattle are discussed.