We reveal the highly structured nature of the Milky Way stellar halo within the footprint of the PAndAS photometric survey from blue main sequence and main sequence turn-off stars. We map no fewer than five stellar structures within a heliocentric range of ~5 to 30 kpc. Some of these are known (the Monoceros Ring, the Pisces/Triangulum globular cluster stream), but we also uncover three well-defined stellar structures that could be, at least partly, responsible for the so-called Triangulum/Andromeda and Triangulum/Andromeda 2 features. In particular, we trace a new faint stellar stream located at a heliocentric distance of ~17 kpc. With a surface brightness of Sigma_V ~ 32-32.5 mag/arcsec^2, it follows an orbit that is almost parallel to the Galactic plane north of M31 and has so far eluded surveys of the Milky Way halo as these tend to steer away from regions dominated by the Galactic disk. Investigating our follow-up spectroscopic observations of PAndAS, we serendipitously uncover a radial velocity signature from stars that have colors and magnitudes compatible with the stream. From the velocity of eight likely member stars, we show that this stellar structure is dynamically cold, with an unresolved velocity dispersion that is lower than 7.1 km/s at the 90-percent confidence level. Along with the width of the stream (300-650 pc), its dynamics points to a dwarf-galaxy-accretion origin. The numerous stellar structures we can map in the Milky Way stellar halo between 5 and 30 kpc and their varying morphology is a testament to the complex nature of the stellar halo at these intermediate distances.