We study the O/Pd(111) system using a lattice-gas Hamiltonian where the many-body interactions among the oxygen adsorbates are derived from a series of density-functional-theory calculations. Through Monte Carlo simulations that employ the Wang-Landau algorithm, we use this Hamiltonian to predict the order-disorder phase-transition temperature as a function of oxygen coverage. We find that oxygen forms ordered p(2x2), (root 3 x root 3)R30 degrees and p(2x1) structures, in agreement with the zero-temperature convex hull, which undergo a continuous transition to a disordered phase upon increasing the temperature. The transition temperature versus coverage curve displays peaks around the coverages corresponding to the formation of the p(2x2) and p(2x1) ordered structures, similar to what has been found from experimental and theoretical studies of the O/Pt(111) and O/Ru(0001) systems.