We present the discovery of a new dwarf galaxy, Hydra II, found serendipitously within the data from the ongoing Survey of the Magellanic Stellar History conducted with the Dark Energy Camera on the Blanco 4 m Telescope. The new satellite is compact ({{r}h}=68 ± 11 pc) and faint ({{M}V}=-4.8 ± 0.3), but well within the realm of dwarf galaxies. The stellar distribution of Hydra II in the color–magnitude diagram is well-described by a metal-poor ([Fe/H]=-2.2) and old (13 Gyr) isochrone and shows a distinct blue horizontal branch, some possible red clump stars, and faint stars that are suggestive of blue stragglers. At a heliocentric distance of 134 ± 10 kpc, Hydra II is located in a region of the Galactic halo that models have suggested may host material from the leading arm of the Magellanic Stream. A comparison with N-body simulations hints that the new dwarf galaxy could be or could have been a satellite of the Magellanic Clouds.