A negative index of refraction in a three-dimensional collection of coated nano-spheres is observed in the terahertz (THz) spectral region. This negative-index metamaterial is a binary composite of two different types of coated nano-spheres (SiO2@SiC/SiO2@AZO); in one type SiO2 spheres coated with a semiconductor (SiC) nano-shell and in another one, nano-shells made of a plasmonic material (AZO). The effective medium parameters derived by extended Maxwell-Garnett (EMG) effective medium theory by specifying the Mie resonances of the coated nano-spheres in the binary composite. The results are supplemented with frequency band structure and transmission curves, calculated by an accurate electromagnetic multiple-scattering technique. The predictions of the EMG theory are in agreement with those of the multiple-scattering technique, providing the effective medium approximation a helpful guide for the experimental works in this field