The study was aimed to estimate genetic parameters for milk production traits of Holstein using random regression models (RRM), and compare the goodness of various RRM with homogeneous and heterogeneous residual variances. A total of 126,980 test-day milk production records of the first parity Holstein cows between 2007 and 2014, from the Dairy Cattle Improvement Center of National Agricultural Cooperative Federation in South Korea, were used in this purpose. These records were milk yield (MILK), fat yield (FAT), protein yield (PROT) and solids-not-fat yield (SNF). The statistical models included random effects of genetic and permanent environments using Legendre polynomials of third to fifth order (L3-L5), fixed effects of herd-test day, and year-season at calving and, a fixed regression for the test-day record (third to fifth order). The residual variances in the models were either homogeneous (HOM) or heterogeneous (15 classes, HET15; 60 classes, HET60). Total 9 models (3 orders of polynomials × 3 types of residual variance) such as L3-HOM, L3-HET15, L3-HET60, L4-HOM, L4-HET15, L4-HET60, L5-HOM, L5-HET15, and L5-HET60 were compared using AIC and/or BIC statistic to find the best fitted model(s) for particular traits. The AIC and BIC estimates were different among models for traits. The lowest BIC value was observed for the model L5-HET15 (MILK; PROT; SNF), and L4-HET15 (FAT), and those fitted the best. The BIC value of HET15 model for a particular polynomial order was lower than that of HET60 model in most cases. The estimated heritabilities from the best-fitted models in the study ranged from 0.08 to 0.15 for MILK, 0.06 to 0.14 for FAT, 0.08 to 0.12 for PROT, and 0.07 to 0.13 for SNF according to days in milk of first lactation. Genetic variances for studied traits tend to decrease at earlier stage of lactation, which then followed by an increase in the middle, and a further decrease at the end of lactation. Estimated RRM parameters can be used in Korean national genetic evaluation system instead of lactation models.