Before Civilization III: Conquests, they were made available with Navigation (Civ3). This change makes it possible to scout foreign shores much eariler since both the Caravel and Explorer are made available at the same time.
See also: Scout
Throughout history there are those whose thirst for adventure led them from the safe confines of civilized lands. These explorers, frequently funded by government stipends, would then journey into the unknown, charting their progress all the way. These expeditions, and the maps they helped create, became blueprints for the conquest and domestication of the once uncharted regions of the world.