First lactation milk yield data consisting of 1,576,102 test-day records for 221,862 Iranian Holstein cows having lactations between 1983 and 2008 were used to study the existence and effect of heterogeneity of variance (HOV) on estimated breeding values and the performance of random regression models (RRMs) with different orders of fit. A pre-correction method based on phenotypic variance, assuming equal heritability for different levels of herd-test date classes and a genetic correlation of one between them, was used to correct for HOV. RRMs with Legendre polynomial functions were used to analyze adjusted and unadjusted records. Some re-ranking of animals occurred from the adjustment, but the correction method only had slight effects on the overall ranking and rank correlations of animals. Data correction had considerable effects on top animals, such that 10% and 17% of top sires and dams, respectively, were replaced from the list of top 1% animals when compared to the homogeneous variance scenario. Application of the adjustment method resulted in slightly higher heritabilities, which may be due to the more accurate estimation of additive genetic effects when HOV is considered. An index consisting of different comparison criteria was used to investigate the effect of HOV on fitting orders of Legendre polynomials and to compare RRMs. In general, the rank of models was improved by increasing the order of fit, but models with smaller orders of fit and correction for HOV performed better than models with higher orders of fit without correction for variance heterogeneity. The results of this research indicate that the accuracy of estimated breeding values may be increased and the genetic progress of the herds could be affected by accounting for HOV as part of genetic evaluations in Iran.