We report the discovery of a giant stellar tidal stream in the halo of NGC 4631, a nearby edge-on spiral galaxy interacting with the spiral NGC 4656, in deep images taken with a 40-cm aperture robotic telescope. The stream has two components: a bridge-like feature extended between NGC 4631 and NGC 4656 (stream_SE) and an overdensity with extended features on the opposite side of the NGC 4631 disk (stream_NW). Together, these features extend more than 85 kpc and display a clear (g-r) colour gradient. The orientation of stream_SE relative to the orientations of NGC 4631 and NGC 4656 is not consistent with an origin from interaction between these two spirals, and is more likely debris from a satellite encounter. The stellar tidal features can be qualitatively reproduced in an N-body model of the tidal disruption of a single, massive dwarf satellite on a moderately eccentric orbit (e=0.6) around NGC 4631 over $sim$ 3.5 Gyr, with a dynamical mass ratio (m1:m2) of ~40. Both modelling and inferences from the morphology of the streams indicate these are not associated with the complex HI tidal features observed between both spirals, which likely originate from a more recent, gas-rich accretion event. The detailed structure of stream_NW suggests it may contain the progenitor of the stream, in agreement with the N-body model. In addition, stream_NW is roughly aligned with two very faint dwarf spheroidal candidates. The system of dwarf galaxies and the tidal stream around NGC 4631 can provide an additional interesting case for exploring the anisotropy distribution of satellite galaxies recently reported in Local Group spiral galaxies by means of future follow-up observations.