A first-principles parameter-free calculation that includes full three-dimensional band structure and dynamical exchange correlations is reported for the dynamical surface response and surface plasmon (SP) on a simple metal prototype surface Mg(0001). We demonstrate that band structure effects have a more profound impact on the SP characteristics than dynamical exchange correlations. A comparison with jellium and one-dimensional potential evaluations shows that the band structure is of paramount importance for the correct description of the SP linewidth and also leads to a better description of the SP energy dispersion. The inclusion of the exchange-correlation kernel results in a better agreement with experimental data. We show that lateral crystal local field effects have a negligible impact on the SP properties. Significant anisotropy is predicted for the SP linewidth.