Na2IrO3 is an intriguing material for which spin-orbit coupling plays a key role. Theoretical predictions have been made that the surface of Na2IrO3 should exhibit a clear signature of the quantum spin Hall effect. We studied the surface of Na2IrO3 using scanning tunneling microscopy and density-functional theory calculations. We observed atomic level resolution of the surface and two types of terminations with different surface periodicity and Na content. By comparing bias-dependent experimental topographic images to simulated images, we determined the detailed atomistic structure of both observed surfaces. One of these reveals a strong relaxation to the surface of Na atoms from the subsurface region two atomic layers below. Such dramatic structural changes well below the surface are highly unusual and cast doubt on any prediction of surface properties based on bulk electronic structure. Indeed, using spatially resolved tunneling spectroscopy, we found no indication of the predicted quantum spin Hall behavior. © 2015 American Physical Society.