Surface nanobubbles are stable gaseous phases in liquids that form on solid substrates. While their existence has been confirmed, there are many open questions related to their formation and dissolution processes along with their structures and properties, which are difficult to investigate experimentally. To address these issues, we carried out molecular dynamics simulations based on atomistic force fields for systems comprised of water, air (N2 and O2), and a Highly Oriented Pyrolytic Graphite (HOPG) substrate. Our results provide insights into the formation/dissolution mechanisms of nanobubbles and estimates for their density, contact angle, and surface tension. We found that the formation of nanobubbles is driven by an initial nucleation process of air molecules and the subsequent coalescence of the formed air clusters. The clusters form favorably on the substrate, which provides an enhanced stability to the clusters. In contrast, nanobubbles formed in the bulk either move randomly to the substrate and spread or move to the water-air surface and pop immediately. Moreover, nanobubbles consist of a condensed gaseous phase with a surface tension smaller than that of an equivalent system under atmospheric conditions, and contact angles larger than those in the equivalent nanodroplet case. We anticipate that this study will provide useful insights into the physics of nanobubbles and will stimulate further research in the field by using all-atom simulations.