A highly sensitive and flexible hydrogen sensor based on organic nanofibers decorated by Pd nanoparticles (NPs) was designed and fabricated for low-concentration hydrogen detection. Pd NPs were deposited on organic nanofiber materials by DC magnetron sputtering. The temperature dependence of the sensitivity at 25 ppm H2 was characterized and discussed, and the maximum response of the sensor increased linearly with increasing measurement temperature. Performances of the hydrogen sensor were investigated with hydrogen concentration ranging from 5 ppm to 50 ppm. This sensor exhibits high sensitivity, with the response up to 6.55% for H2 as low as 5 ppm, and the output response of the hydrogen sensor increased linearly with the square root of hydrogen concentration. A cycling test between pure nitrogen and 25 ppm hydrogen concentration was performed, and the hydrogen sensor exhibited excellent consistency.