We present the first near-IR scattered light detection of the transitional disk associated with the Herbig Ae star MWC 758 using data obtained as part of the Strategic Exploration of Exoplanets and Disks with Subaru, and 1.1 micron HST/NICMOS data. While sub-millimeter studies suggested there is a dust-depleted cavity with r=0.35, we find scattered light as close as 0.1 (20-28 AU) from the star, with no visible cavity at H, K, or Ks. We find two small-scaled spiral structures which asymmetrically shadow the outer disk. We model one of the spirals using spiral density wave theory, and derive a disk aspect ratio of h ~ 0.18, indicating a dynamically warm disk. If the spiral pattern is excited by a perturber, we estimate its mass to be 5+3,-4 Mj, in the range where planet filtration models predict accretion continuing onto the star. Using a combination of non-redundant aperture masking data at L and angular differential imaging with Locally Optimized Combination of Images at K and Ks, we exclude stellar or massive brown dwarf companions within 300 mas of the Herbig Ae star, and all but planetary mass companions exterior to 0.5. We reach 5-sigma contrasts limiting companions to planetary masses, 3-4 MJ at 1.0 and 2 MJ at 1.55 using the COND models. Collectively, these data strengthen the case for MWC 758 already being a young planetary system.