Shallow nitrogen-vacancy (NV) center in diamond is promising in quantum sensing applications however its sensitivity has been limited by surface terminators and defects. There is an immediate quest to find suitable diamond surfaces for NV sensors. In this work, the surface terminators of (113) diamond to host shallow NV centers are studied by means of first principles calculations. Results indicate that complete oxygen termination of (113) diamond creates positive electron affinity with neither strain on the surface nor in-gap levels. This is a very surprising result as the commonly employed oxygenated (001) diamond surface is often defective due to the disorder created by the strain of ether groups at the surface that seriously undermine the coherence properties of the shallow NV centers. The special atomic configurations on (113) diamond surface are favorable for oxygen bonding, in contrast to (001) and (111) diamond surfaces. These simulations imply that oxygenated diamond (113) surface can be produced by conventional diamond chemical vapor deposition growth. Combining this with the ∼73% preferential alignment of as-grown NV centers in (113) oriented diamond, oxygenated (113) diamond is presently supposed to be the most prospective host for NV quantum sensors.