We present the first experimental realization of a terahertz (THz) waveguide that exhibits a negative effective index of refraction. To demonstrate this, we designed fabricated and characterized a linear array of three-dimensional structures that consist of split ring resonators and posts. THz radiation is launched and guided in the form of surface plasmon polaritons (SPPs) along the 3D metallic structures. Using THz time-domain spectroscopy, we measure the temporal evolution of the propagating THz SPP, which yields the evidence of a negative refractive index.