Desorption of adsorbates from material surfaces occurs through the interaction of the adsorbate with the surface phonons. In this work, a phonon master equation model is used to study desorption of adsorbates from carbon surfaces. The adsorbate-phonon interaction is modeled as a surface-adsorbed anharmonic oscillator undergoing a random walk driven by thermal fluctuations in the lattice. Desorption results from a random walk that leads to a continuum state of the oscillator. A new semi-classical model is introduced in which, molecular dynamics is used to quantify the thermal fluctuations, which are then used to compute the transition rates using the density matrix formulation. The new model has been validated using the desorption rate constants for the previously studied system of CO adsorbed on copper. The rate constants for O desorption from top and bridge site configurations of the graphite surfaces are presented. The importance of representing the atomic interactions accurately is demonstrated. The rate constants obtained cannot always be modeled by the simple Arrhenius rate equation.