In this study, we systematically investigated the influences of nitrogen content and grain size on the tensile properties and deformation behaviors of titanium at room temperature. By high-pressure torsion and annealing, we obtained ultrafine-grained (UFG) Ti-0.3 wt%N alloy with a fully recrystallized microstructure, which combined an unprecedented synergy of ultrahigh yield strength (1.04 GPa) and large uniform elongation (10%). The hardening and strain-hardening mechanisms of Ti-0.3 wt%N alloy were comprehensively studied via deformation substructure observation and first-principles calculations. It is revealed that the contributions of nitrogen to the excellent strength/ductility balance in UFG Ti-0.3 wt%N were twofold. On one hand, nitrogen atoms inside the grains strongly impeded the motion of <a> dislocations on prismatic plane due to the shuffling of nitrogen from octahedral to hexahedral site, giving rise to a six-fold increase in the friction stress relative to pure Ti. Moreover, the greatly reduced stacking fault energy difference between prismatic and pyramidal planes in Ti-0.3 wt%N alloy facilitated an easier activation of <c+a> dislocations, which contributed to an enhanced strain-hardening rate. On the other hand, some nitrogen atoms segregated near the grain boundaries, a phenomenon discovered in α-titanium for the first time. These segregated nitrogen atoms served as an additional contributor to the high yield strength of UFG Ti-0.3 wt%N, by raising the barrier against dislocation slip transfer between grains. Our experimental and theoretical calculation work provide insights for the design of affordable high strength titanium without a large sacrifice of ductility, shedding lights on a more widespread use of this high strength to weight ratio material.