We use the SDSS-Gaia Catalogue to identify six new pieces of halo substructure. SDSS-Gaia is an astrometric catalogue that exploits SDSS data release 9 to provide first epoch photometry for objects in the Gaia source catalogue. We use a version of the catalogue containing $245316$ stars with all phase space coordinates within a heliocentric distance of $\sim 10$ kpc. We devise a method to assess the significance of halo substructures based on their clustering in velocity space. The two most substantial structures are multiple wraps of a stream which has undergone considerable phase mixing (S1, with 94 members) and a kinematically cold stream (S2, with 61 members). The member stars of S1 have a median position of ($X,Y,Z$) = ($8.12,-0.22,2.75$) kpc and a median metallicity of [Fe/H] $=-1.78$. The stars of S2 have median coordinates ($X,Y,Z$) = ($8.66,0.30,0.77$) kpc and a median metallicity of [Fe/H] $=-1.91$. They lie in velocity space close to some of the stars in the stream reported by Helmi et al. (1999). By modelling, we estimate that both structures had progenitors with virial masses $\approx 1010M\odot$ and infall times $\gtrsim 9$ Gyr ago. Using abundance matching, these correspond to stellar masses between $106$ and $107M\odot$. These are somewhat larger than the masses inferred through the mass-metallicity relation by factors of 5 to 15. Additionally, we identify two further substructures (S3 and S4 with 55 and 40 members) and two clusters or moving groups (C1 and C2 with 24 and 12) members. In all 6 cases, clustering in kinematics is found to correspond to clustering in both configuration space and metallicity, adding credence to the reliability of our detections.