The hydrophobic interaction has been studied extensively over the past few decades with only partial success. Several mechanisms have been proposed to explain this ubiquitous force but none was fully established. Experimentally, the force has been studied in great detail at distances larger than 2-3 nanometers where the static AFM and the surface force apparatus that served those measurements were stable. Little is known about the short-range interaction and even its sign. Using a high resolution FM-AFM, which was free of that instability, we succeeded in measuring the full distance depended force and found that the hydrophobic attraction seen at long distances turns into pronounced repulsion at shorter distances (that may nevertheless reach ~3 nanometers) coupled to an oscillatory force profile. The short-range repulsion with the oscillatory force profile, as well as the longer range attraction were traced to the accumulation of air near the hydrophobic surfaces. The newly discovered mechanism of hydrophobic attraction and repulsion is expected to be relevant to practically all natural and technological systems of interest.