Fatigue is a condition that affects any character travelling water that is too deep, such as the oceans surrounding the continents.
Close to land, the ocean floor is generally not very far below sea level, and it can usually be seen from the surface; at greater distances from the shore, the floor recedes deeper and deeper. When the depth of the water reaches a certain point, swimming in the region causes a Fatigue bar to appear, which displaying a player's weariness. It behaves similar to the Breath bar; the bar will deplete over time (the Fatigue bar depletes much faster than the Breath bar, it matches the rate at which the Breath bar originally depleted), and will deal damage to the player when it reaches zero. The Fatigue bar and Fatigue damage occurs regardless of the player's depth. (i.e. swimming on the surface, diving, water walking or even flying over a Fatigue region will cause this). Players may swim back toward shallower waters to refill the fatigue bar and avoid death. Fatigue also affects players in ghost form, as the player who is attempting to navigate as a ghost will simply die once more as a ghost (and inflict a second durability penalty) and have to return to their body or resurrect at the Spirit Healer. Hunter pets seem to be affected by Fatigue as well; however, they display no Fatigue bar to show their weariness. The Fatigue damage can be seen in the Combat Log.
Fatigue exists to prevent players from straying too far from land and reaching areas that are unfinished. It also serves as a natural boundary enclosing zones. You can see a Fatigue region when the ocean floor seems to slope downward endlessly. Don't bother trying to reach the absolute bottom of the ocean, as even if you survive the Fatigue damage long enough to reach it, there is a barrier at a certain depth below sea-level which kills all characters, similar to the death barriers you encounter whilst falling off the edges in Outland.
Fatigue is not associated with time spent swimming. Because of fatigue mechanics, there are a few "normal" areas in the World of Warcraft where fatigue erroneously occurs, such as one small strip of the Vile Reef. Fatigue never occurs in inland lakes, or rivers, no matter how long you swim. Fatigue zones can be easily identified by a darker color on the surface of the water than surrounding areas (also visible in the minimap. If swimming an unusual route (for example, from Zoram Strand to Shadowprey Village) you must tightly hug the shoreline in places to prevent fatigue, although you may save some time by swimming through the Fatigue area, provided you can be sure to clear it before the bar is depleted.
While in a Fatigue zone, mana regeneration, both regular and while casting (mp5) will cease, meaning it is almost impossible to survive in Fatigue water indefinitely. Some spells and abilities, as well as potions may still be useful to regenerate mana while Fatigued, but the easiest way to regain mana is to enter safer water.
Before this mechanic was in place, low level characters, who have low health pools, high health regeneration (proportional to their total health), and very powerful and mana-efficient heals (again, proportional to their total health), could swim indefinitely in Fatigue water, as their mana regenerated entirely in the time it took for Fatigue to do damage equal the amount healed. The mechanic also increases the difficulty of higher level characters who try to swim through Fatigue.
The damage done is equal to 20% of your max HP every 2 seconds. It is possible to reduce the damage of every tick by removing any gear or buffs that grant bonus HP or stamina, but this often comes at the cost of losing mana required for healing through the Fatigue itself.
Although the fatigue timer cannot be slowed, players may extend the distance they swim through various means: , a druid's Aquatic Form, and Water Walking/Path of Frost can increase the speed at which players travel through or over water. With 2/2 On a Pale Horse, a Death Knight can make a mounted run between Teldrassil and Darkshore without dying from fatigue. See Swim#Methods to increase swim speed for the full list.
Damage done by fatigue can be healed, though the means of healing are limited by the mana regeneration restrictions mentioned above. Potions can supplement the limited healing received while Fatigued, but their cooldowns are too long to rely on the potions alone for survival.
Note that swimming between continents is impossible even without fatigue as Kalimdor, the Eastern Kingdoms, the Azuremyst Isles, and Northrend exist in different "instances". For example, a player swimming from Kalimdor due east would reach the end of the Kalimdor map and weird emptiness beyond, not the Eastern Kingdoms or into other areas where they aren't wanted.
Fatigue-negating techniques are actually required to travel to the Islands south of Land's End Beach in Tanaris, which are involved in the Ahn'Qiraj Scepter questline, although it is possible to reach these islands before the Fatigue bar becomes depleted.
This section concerns content exclusive to Cataclysm.
With the introduction of being able to use flying mounts in Azeroth, the Fatigue meter has taken on a bigger importance. The Grand Master riding skill can make a mount be able to beat the Fatigue system in order to take unintended shortcuts, such as one that someone can do to get from Stormwind directly to Dun Morogh by going north from Stormwind (thereby passing two or three other zones you would normally have to travel through). Also, someone might be able to beat it if they travel from the dock in Terdrassil to the cost of Darkshore. Finally, someone could beat the Fatigue bar to get from Dun Morogh to the on-land Flight Master in Vashj'ir. As the Vanilla continents (Eastern Kingdoms and Kalimdor) are shaped more erratically than Outland and Northrend, especially Eastern Kingdoms, players will have to be more careful as to when and if the meter procs when using flying mounts because of the shape of the land.