A novel, to the best of our knowledge, sensor architecture for palladium-coated fiber Bragg gratings is proposed and demonstrated that allows highly accurate multi-parameter sensing and decoupling of hydrogen concentration from temperature. By means of partly Pd-coated Pi-shifted FBGs (PSFBGs), the notch wavelength of the narrow transmission band and the flank wavelength of the broader reflection band experience different hydrogen and temperature sensitivities. PSFBGs were calibrated at hydrogen concentrations between 800 and 10,000 ppm and temperatures from 20 to 40°C, and a decreased hydrogen sensitivity at increased temperatures was found. Nonlinear temperature-dependent hydrogen calibration functions were therefore determined. An iterative matrix algorithm was used to decouple hydrogen concentration and temperature and to account for the nonlinear calibration functions. Achieved improvements and results have great importance for real field applications of FBG-based hydrogen sensing.