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 κ 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 s = 14.6 ± 0.4, and L' = 13.12 ± 0.09 indicate a temperature of ~1700 K. The galactic kinematics of the host star are consistent with membership in the Columba Association, implying a corresponding age of 30+20 –10 Myr. The system's age, combined with the companion photometry, points to a model-dependent companion mass ~12.8 M Jup. The host star's estimated mass of 2.4-2.5 M ☉ 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.