We report the discovery of a tight substellar companion to the young solar analog PZ Tel, a member of the Beta Pictoris moving group observed with high contrast adaptive optics imaging as part of the Gemini NICI Planet-Finding Campaign. The companion was detected at a projected separation of 16.4 +/- 1.0 AU (0.33 +/- 0.01") in April 2009. Second-epoch observations in May 2010 demonstrate that the companion is physically associated and shows significant orbital motion. Monte Carlo modeling constrains the orbit of PZ Tel B to eccentricities > 0.6. The near-IR colors of PZ Tel B indicate a spectral type of M7+/-2 and thus this object will be a new benchmark companion for studies of ultracool, low-gravity photospheres. Adopting an age of 12 +8 -4 Myr for the system, we estimate a mass of 36 +/- 6 Mjup based on the Lyon/DUSTY evolutionary models. PZ Tel B is one of few young substellar companions directly imaged at orbital separations similar to those of giant planets in our own solar system. Additionally, the primary star PZ Tel A shows a 70 um emission excess, evidence for a significant quantity of circumstellar dust that has not been disrupted by the orbital motion of the companion. ; Comment: 15 pages, 4 figures, to appear in ApJ Letters