Required fishing skill
Each zone has an associated level of fishing that defines the difficulty of catching a fish. The higher your fishing skill is in relation to the level that a zone requires, the easier it will be to catch fish. If your skill is below the zone's requirement, you will catch junk items rather than fish. As of Patch 3.1, there is no longer a minimum skill level required to fish in a zone, and the former 100% catch rate (no get-aways) level is now the 100% fish (no junk) level.
The skill required to guarantee catching fish in a zone is usually about 5 times the average level of monsters in the zone, although some zones vary considerably from this rule of thumb.
Based upon data collected by El's Extreme Anglin', these are the approximate fishing skill levels required:
||Skill for 100% fish (no junk) catch rate
||Level 1-10 zones: Racial starting zones, outside of cities: Azuremyst Isle, Dun Morogh, Durotar, Elwynn Forest, Eversong Woods, Gilneas, Lost Isles, Mulgore, Teldrassil, and Tirisfal Glades
||Level 11-20 zones: Azshara (General), Blackfathom Deeps, Bloodmyst Isle, Darkshore, The Deadmines, Ghostlands, Ruins of Gilneas, Loch Modan, Northern Barrens (except Oasis), Redridge Mountains (General), Silverpine Forest, Wailing Caverns, and Westfall
Racial Capital Cities: Darnassus, Ironforge, Orgrimmar, Stormwind, Thunder Bluff, Undercity
||Northern Barrens (Oasis)
||Level 21-30 zones: Arathi Highlands (General), Ashenvale, Duskwood, Hillsbrad Foothills, Northern Stranglethorn (General), Redridge Mountains (Lake Everstill), Stonetalon Mountains, and Wetlands
||Level 31-40 zones: Arathi Highlands (Forbidding Sea), Cape of Stranglethorn, Desolace, Dustwallow Marsh, Feralas (General), Forbidding Sea, Great Sea, Hinterlands, Scarlet Monastery, Southern Barrens, and Western Plaguelands
||Level 40-55 zones: Badlands, Eastern Plaguelands, Felwood, Moonglade, Tanaris, Temple of Atal'Hakkar, and Thousand Needles
||Azeroth: Un'Goro Crater (General)
Outland: Hellfire Peninsula, Nagrand (Forge Camp: Hate), and Shadowmoon Valley
||Outland: Zangarmarsh east of Serpent Lake, and The Lagoon
||Level 55-60 zones and other difficult-to-fish areas: Azshara (Bay of Storms, Hetaera's Clutch and Scalebeard's Cave only), Blasted Lands (Coastal), Deadwind Pass, Dire Maul, Feralas (Jademir Lake), Scholomance, Searing Gorge, Silithus, Stratholme, Swamp of Sorrows, Winterspring, and Zul'Aman
||Azeroth: Isle of Quel'Danas
Outland: Serpent Lake and West in Zangarmarsh, Ground level in Terokkar Forest
||Outland: Nagrand east of Halaa including Elemental Plateau, Eco-Dome Midrealm in Netherstorm
Northrend: Borean Tundra, Dragonblight, Grizzly Hills, Howling Fjord
||Outland: Nagrand: Lake Sunspring and Skysong Lake
||Outland: Terokkar Forest: Silmyr Lake, Blackwind Lake, Lake Ere'Noru and Lake Jorune
Northrend: Crystalsong Forest
||Northrend: Dalaran, Sholazar Basin, and Wintergrasp
||The Maelstrom: Deepholm
Northrend: Hrothgar's Landing, Icecrown, The Storm Peaks, and Ulduar
||Northrend: The Frozen Sea
Azeroth: Mount Hyjal (General) and Vashj'ir
||Northrend: The Ruby Sanctum
Azeroth: Twilight Highlands and Uldum
||Azeroth: Tol Barad
Silmyr Lake was raised in to the highest fishing tier in patch 2.4. With the addition of the Wrath of the Lich King expansion, Northrend now has many zones which exceed this tier.
The lowest fishing skill, trained as an apprentice with no experience, is 1. Training is required in order to use a fishing pole to fish, so the lowest skill required is 1.
Note that the highest unaided fishing skill that a character can have is 450. Ensuring a catch in the upper tiers (up to 575) requires gear with bonuses to fishing skill. The bonuses to fishing skill from equipped items stack.
Fishing skill above the skill required for 100% catch rate is wasted, so you do not always need to equip a lure. For example, fishing in tier 1, the +25 fishing skill [Shiny Bauble] lure would be helpful when you are first starting out, but once you've caught around 30 fish, it would be superfluous to use a lure in the starting area.