Na2IrO3 is an intriguing material for which spin-orbit coupling plays a key role. Theoretical predictions, so far unverified, 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 at the surface 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.