We find a new substellar companion to the Pleiades member star, Pleiades HII 3441, using the Subaru telescope with adaptive optics. The discovery is made as part of the high-contrast imaging survey to search for planetary-mass and substellar companions in the Pleiades and young moving groups. The companion has a projected separation of 0.49 +/- 0.02 (66 +/- 2 AU) and a mass of 68 +/- 5 M_J based on three observations in the J-, H-, and K_S-band. The spectral type is estimated to be M7 (~2700 K), and thus no methane absorption is detected in the H band. Our Pleiades observations result in the detection of two substellar companions including one previously reported among 20 observed Pleiades stars, and indicate that the fraction of substellar companions in the Pleiades is about 10.0 +26.1/-8.8 %. This is consistent with multiplicity studies of both the Pleiades stars and other open clusters.