The formation of surface oxides on metal surfaces is not only important in materials science, but also of significance in heterogeneous catalysis due to the fact that during most oxidation reactions the metal catalysts are inevitably oxidized, which may cause dramatic consequences in the reactions. In this work, we perform a thorough investigation on the formation of surface oxides on Pd(211) using advanced first principles calculations. A detailed mechanism of the surface oxide formation is revealed: starting from simple O chemisorption, the step sites of Pd(211) are oxidized by formation of local linear O-Pd-O oxide structures and then planar Pd-O4 structures as the O coverage is increased; the local oxide structures spread out to yield a surface oxide layer, and finally 3-dimesional oxide forms with the increase of the degree of surface oxidation. The structures of O-Pd-O and Pd-O4 are revealed to be the basic units for oxide formation and can be considered as the oxide seeds. The origin of the oxide seed formation is identified, and the understanding of the oxide formation process is provided. A simple equation is derived, which describes the general trend of O vacancy formation in the oxides. The equation may be of great use for understanding oxide formation on Pd surfaces.