The surface of Ti-29Nb-13Ta-4.6Zr (TNTZ) subjected to gas nitriding at 1023–1223 K was investigated in comparison with the conventional biomedical titanium alloy, Ti-6Al-4V ELI (Ti64). After gas nitriding, the microstructures near the surface of these alloys were observed by optical microscopy, X-ray diffraction, Auger electron spectroscopy, and X-ray photoelectron spectroscopy. In both alloys, two titanium nitrides (TiN and Ti2N) are formed and the α phase precipitated by gas nitriding. Furthermore, oxygen impurity in the gas nitriding atmosphere reacts with the titanium nitrides; thus, TiO2 is formed at the outermost titanium nitride layer. The surface hardening was also evaluated by Vickers hardness measurement. The Vickers hardness near the surface of TNTZ and Ti64 increases significantly by gas nitriding.