We present the discovery of a candidate substellar companion from a survey of nearby, young stars with the NICMOS coronagraph on the Hubble Space Telescope. The H ~ 12 mag object was discovered approximately 4" from the young A0V star HR 7329. Using follow-up spectroscopy from STIS, we derive a spectral type between M7V and M8V with an effective temperature of ~ 2600 K. We estimate that the probability of a chance alignment with a foreground dwarf star of this nature is ~ 10^(-8) and therefore suggest the object (HR 7329B) is physically associated with HR 7329 with a projected separation of 200 AU. Current brown dwarf cooling models indicate a mass of less than 50 Jupiter masses for HR 7329B based on age estimates of < 30 Myr for HR7329A.