We present new optical coronagraphic data of Fomalhaut obtained with HST/STIS in 2010 and 2012. Fomalhaut b is recovered at both epochs to high significance. The observations include the discoveries of tenuous nebulosity beyond the main dust belt detected to at least 209 AU projected radius, and a 50 AU wide azimuthal gap in the belt northward of Fomalhaut b. The two epochs of Space Telescope Imaging Spectrograph (STIS) photometry exclude optical variability greater than 35%. A Markov chain Monte Carlo analysis demonstrates that the orbit of Fomalhaut b is highly eccentric, with e = 0.8 ± 0.1, a = 177 ± 68 AU, and q = 32 ± 24 AU. Fomalhaut b is apsidally aligned with the belt and 90% of allowed orbits have mutual inclination ≤36°. Fomalhaut b's orbit is belt crossing in the sky plane projection, but only 12% of possible orbits have ascending or descending nodes within a 25 AU wide belt annulus. The high eccentricity invokes a dynamical history where Fomalhaut b may have experienced a significant dynamical interaction with a hypothetical planet Fomalhaut c, and the current orbital configuration may be relatively short-lived. The Tisserand parameter with respect to a hypothetical Fomalhaut planet at 30 AU or 120 AU lies in the range 2-3, similar to highly eccentric dwarf planets in our solar system. We argue that Fomalhaut b's minimum mass is that of a dwarf planet in order for a circumplanetary satellite system to remain bound to a sufficient radius from the planet to be consistent with the dust scattered light hypothesis. In the coplanar case, Fomalhaut b will collide with the main belt around 2032, and the subsequent emergent phenomena may help determine its physical nature. © 2013. The American Astronomical Society. All rights reserved.