Magnetic skyrmions are two-dimensional magnetization swirls that stack in the form of tubes in the third dimension and which are proposed as prospective information carriers for nonvolatile memory devices due to their unique topological properties. From resonant elastic X-ray scattering measurements on Cu2OSeO3 with an in-plane magnetic field, we find that a state of perpendicularly ordered skyrmions forms, in stark contrast to the well-studied bulk state. The surface state is stable over a wide temperature range, unlike the bulk state in out-of-plane fields which is confined to a narrow region of the temperature-field phase diagram. In contrast to ordinary skyrmions found in the bulk, the surface state skyrmions result from the presence of magnetic interactions unique to the surface which stabilize them against external perturbations. The surface guiding makes the robust state particular interesting for racetracklike devices, ultimately allowing for much higher storage densities due to the smaller lateral footprint of the perpendicular skyrmions.