Plasmonic sensors rely on optical resonances in metal nanoparticles and are typically limited by their broad spectral features. This constraint is particularly taxing for optical hydrogen sensors, in which hydrogen is absorbed inside optically-lossy Pd nanostructures and for which state-of-the-art detection limits are only at the low parts-per-million (ppm) range. Here, we overcome this limitation by inversely designing a plasmonic metasurface based on a periodic array of Pd nanoparticles. Guided by a particle swarm optimization algorithm, we numerically identify and experimentally demonstrate a sensor with an optimal balance between a narrow spectral linewidth and a large field enhancement inside the nanoparticles, enabling a measured hydrogen detection limit of 250 parts-per-billion (ppb). Our work significantly improves current plasmonic hydrogen sensor capabilities and, in a broader context, highlights the power of inverse design of plasmonic metasurfaces for ultrasensitive optical (gas) detection.