We carried out a spectroscopic follow-up program of the four new stellar stream candidates detected by Belokurov & Koposov (2016) in the outskirts of the Large Magellanic Cloud (LMC) using FORS2 (VLT). The medium-resolution spectra were used to measure the line-of-sight velocities, estimate stellar metallicities and to classify stars into Blue Horizontal Branch (BHB) and Blue Straggler (BS) stars. Using the 4-D phase-space information, we attribute approximately one half of our sample to the Magellanic Clouds, while the rest is part of the Galactic foreground. Only two of the four stream candidates are confirmed kinematically. While it is impossible to estimate the exact levels of MW contamination, the phase-space distribution of the entire sample of our Magellanic stars matches the expected velocity gradient for the LMC halo and extends as far as 33 deg (angular separation) or 29 kpc from the LMC center. Our detections reinforce the idea that the halo of the LMC seems to be larger than previously expected, and its debris can be spread in the sky out to very large separations from the LMC center. Finally, we provide some kinematic evidence that many of the stars analysed here have likely come from the Small Magellanic Cloud.