We identify velocity channel map intensities as a new way to trace magnetic fields in turbulent media. This work makes use of both the modern theory of magnetohydrodynamic (MHD) turbulence, which predicts that magnetic eddies are aligned with the local direction of the magnetic field, and also the theory of spectral line position-position-velocity (PPV) statistics, which describes how velocity and density fluctuations are mapped onto PPV space. In particular, we use the fact that the fluctuations of the intensity of thin channel maps are mostly affected by the turbulent velocity, while the thick maps are dominated by density variations. We study how contributions of the fundamental MHD modes affect the Velocity Channel Gradients (VChGs), and demonstrate that the VChGs arising from Alfvén and slow modes are aligned perpendicular to the local direction of the magnetic field, while the VChGs produced by the fast mode are aligned parallel to the magnetic field. The dominance of Alfvén and slow modes in interstellar media will therefore allow reliable magnetic field tracing using the VChGs. We explore ways of identifying self-gravitating regions that do not require polarimetric information. In addition, we also introduce a new measure, termed "Reduced Velocity Centroids" (RVCGs), and compare its abilities with those of VChGs. We employed VChGs in analyzing GALFA 21 cm data and successfully compared the magnetic field directions with the Planck polarization observations. The applications of the suggested techniques include both tracing the magnetic field in diffuse interstellar media and star-forming regions, and removing the galactic foreground in the framework of cosmological polarization studies.