We present the direct imaging discovery of an extrasolar planet, or possible low-mass brown dwarf, at a projected separation of 55 {+-} 2 AU (1.''058 {+-} 0.''007) from the B9-type star {kappa} And. The planet was detected with Subaru/HiCIAO during the SEEDS survey and confirmed as a bound companion via common proper motion measurements. Observed near-infrared magnitudes of J = 16.3 {+-} 0.3, H = 15.2 {+-} 0.2, K{sub s} = 14.6 {+-} 0.4, and L' = 13.12 {+-} 0.09 indicate a temperature of {approx}1700 K. The galactic kinematics of the host star are consistent with membership in the Columba Association, implying a corresponding age of 30{sup +20}{sub -10} Myr. The system's age, combined with the companion photometry, points to a model-dependent companion mass {approx}12.8 M{sub Jup}. The host star's estimated mass of 2.4-2.5 M{sub Sun} places it among the most massive stars ever known to harbor an extrasolar planet or low-mass brown dwarf. While the mass of the companion is close to the deuterium burning limit, its mass ratio, orbital separation, and likely planet-like formation scenario imply that it may be best defined as a 'super-Jupiter' with properties similar to other recently discovered companions to massive stars.