While H2 is indispensable as a green fuel source, it is highly flammable and explosive. Because it is difficult to detect due to its lack of odor and color, a solution for proper monitoring of H2 leakage is essential to ensure safe handling. To this end, we have successfully fabricated hollow Pd-Sn alloy nanotubes (NTs) through electrospinning and a subsequent etching method, which is the first demonstration of synthesizing Pd-based hollow alloy nanofibers with ultrafine grain sizes. We found that the alloying of Pd with Sn could effectively prevent degradation of the sensing performance upon the alpha-beta phase transition during hydrogen detection. Besides, the highly porous structure with smaller nanograins offered more exposed active sites and higher gas accessibility to bulk materials. The resultant Pd-Sn NTs exhibited excellent sensitivity toward H2 (0.00005-3%). Notably, the limit of detection of 0.0001% is an outstanding achievement on H2 sensing among state-of-the-art H2 sensors. Moreover, when exposed to a high concentration of H2 (3%), Pd-Sn NTs showed excellent cycling stability with a standard deviation of 0.07% and a sensitivity of 9.27%. These obtained sensing results indicate that Pd-Sn NTs can be used as a highly sensitive and stable H2 gas sensor at room temperature (25 degrees C).