We present the discovery of three protoclusters at z~3-4 with spectroscopic confirmation in the Canada-France-Hawaii Telescope Legacy Survey Deep Fields. In these fields, we investigate the large-scale projected sky distribution of z~3-6 Lyman-break galaxies and identify 21 protocluster candidates from regions that are overdense at more than 4{sigma} overdensity significance. Based on cosmological simulations, it is expected that more than 76% of these candidates will evolve into a galaxy cluster of at least a halo mass of 10^14^ M_{sun}_ at z=0. We perform follow-up spectroscopy for eight of the candidates using Subaru/FOCAS, Keck II/DEIMOS, and Gemini-N/GMOS. In total we target 462 dropout candidates and obtain 138 spectroscopic redshifts. We confirm three real protoclusters at z=3-4 with more than five members spectroscopically identified and find one to be an incidental overdense region by mere chance alignment. The other four candidate regions at z~5-6 require more spectroscopic follow-up in order to be conclusive. A z=3.67 protocluster, which has 11 spectroscopically confirmed members, shows a remarkable core-like structure composed of a central small region (<0.5 physical Mpc) and an outskirts region (~1.0 physical Mpc). The Ly{alpha} equivalent widths of members of the protocluster are significantly smaller than those of field galaxies at the same redshift, while there is no difference in the UV luminosity distributions. These results imply that some environmental effects start operating as early as at z~4 along with the growth of the protocluster structure. This study provides an important benchmark for our analysis of protoclusters in the upcoming Subaru/HSC imaging survey and its spectroscopic follow-up with the Subaru/PFS that will detect thousands of protoclusters up to z~6.