Experiments show that bubbles covered with monodisperse polystyrene particles, with particle to bubble radius ratios of about 0.1, evolve to form faceted polyhedral shapes that are stable to dissolution in air-saturated water. We perform Surface Evolver simulations and find that the faceted particle-covered bubble represents a local minimum of energy. At the faceted state, the Laplace overpressure vanishes, which together with the positive slope of the bubble pressure-volume curve, ensures phase stability. The repulsive interactions between the particles cause a reduction of the curvature of the gas-liquid interface, which is the mechanism that arrests dissolution and stabilizes the bubbles.