Adopting the Standard Halo Model (SHM) of an isotropic Maxwellian velocity distribution for dark matter (DM) particles in the Galaxy, the most stringent current constraints on their spin-dependent scattering cross-section with nucleons come from the IceCube neutrino observatory and the PICO-60 C3F8 superheated bubble chamber experiments. The former is sensitive to high energy neutrinos from the self-annihilation of DM particles captured in the Sun, while the latter looks for nuclear recoil events from DM scattering off nucleons. Although slower DM particles are more likely to be captured by the Sun, the faster ones are more likely to be detected by PICO. Recent N-body simulations suggest significant deviations from the SHM for the smooth halo component of the DM, while observations hint at a dominant fraction of the local DM being in substructures. We use the method of Ferrer et al. (JCAP 1509: 052, 2015) to exploit the complementarity between the two approaches and derive conservative constraints on DM-nucleon scattering. Our results constrain σSD3×10−39cm2(6×10−38cm2) at 90% C.L. for a DM particle of mass 1 TeV annihilating into τ+τ−(b ̄b) with a local density of ρDM=0.3GeV/cm3. The constraints scale inversely with ρDM and are independent of the DM velocity distribution.