Cutting parameters and material properties have important effects on the quality of milled surface, which can be characterized by fractal dimension and surface roughness. The relationships between two surface parameters (surface roughness and fractal dimension) and material hardness, elongation, spindle speed and feed rate were investigated, respectively, in this study. Four carbon steels, that is, AISI 1020, Gr 50, 1045 and 1566, were milled with five spindle speeds and four feed rates on a computer numerical control machine. The surface topographies were measured with a three-dimensional profiler. The surface profiles were obtained by re-sampling the data points on the surface topography in the measurement direction. The surface roughness and fractal dimension were calculated from the two-dimensional profiles, where the fractal dimension was obtained by the root-mean-square method. The results showed that for specific spindle speed and feed rate, the roughness of the milled surface decreased with the workpiece hardness, whereas the elongation and fractal dimension increased with the hardness. Based on the material hardness and elongation, spindle speed and feed rate, empirical formulae were established to quantitatively estimate the surface roughness and fractal dimension. Moreover, the spindle speed and feed rate can be easily calculated from the empirical formulae to achieve a surface with the desired surface roughness and fractal dimension. The empirical formulae have been demonstrated with the experiments and were shown to be applicable in estimating the surface roughness and fractal dimension for all carbon steels in end milling. The results are instructive for the fractal dimension estimation of the machined surfaces of carbon steel, which has not been previously studied.