New oceanographic observations in the Gulf of Aden in the northwestern Indian Ocean have revealed large, energetic, deep-reaching mesoscale eddies that fundamentally influence the spreading rates and pathways of intermediate-depth Red Sea Water (RSW). Three eddies were sampled in February 2001, two cyclonic and one anticyclonic, with diameters 150--250 km. Both cyclones had surface-intensified velocity structure with maxima ~0.5 m s-1, while the equally-energetic anticyclone appeared to be decoupled from the surface circulation. All three eddies reached nearly to the 1000--2000 m deep sea floor, with speeds as high as 0.2--0.3 m s-1 extending through the depth range of RSW. Comparison of salinity and direct velocity measurements indicates that the eddies advect and stir RSW through the Gulf of Aden. Anomalous water properties in the center of the anticyclonic eddy point to a possible formation site in the Somali Current System.