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 (SMASH) conducted with the Dark Energy Camera on the Blanco 4m 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 HydraII 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.