Alliance Fishing & Cooking Guide

Alliance

Best place to start is in Elwynn Forest.
Go speak to Nyoma by Crystal Lake and buy the recipes for Brilliant Smallfish and Longjaw Mud Snappers. Now start fishing in Crystal Lake.
You'll want to catch about 60 Brilliant Smallfish to get your cooking from 1 to 50.
Now go to Stormwind City and fish the canals for Longjaw Mud Snappers. You'll need about 50 of them to raise your cooking to 100.
Between levels 50 and 75 go learn journeyman fishing and cooking.
Now go to Southshore and speak to Donald Rabonne and buy the recipes for Bristle Whisker Catfish and Mithril Head Trout.
Go to the river to the east of Southshore and fish for Bristle Whisker Catfish. You'll need about 80-100 of these to get your cooking to level 175.
Between levels 125 and 150 go learn expert cooking from trainer. You'll need to go to Booty Bay and buy a book for your Fishing level. Speak to Old Man Heming and buy the book Expert Fishing: The Bass and You.
Now go to the Lakes outside Stromgarde Keep in Arathi Highlands and fish for Mithril Head Trout. Your going to need about 60 of these to get your cooking up to level 225.

At this point you should now have level 225 fishing and level 225 cooking. If your not level 35 yet, then this is as far as you can go. If you are level 35+ then you have two quests to complete before you can continue.

First quest: Cooking
Requirements: Level 35, 225 Cooking.

Go to Gadgetzan in Tanaris and speak to Dirge Quikcleave. He is in the tavern. He'll want you to bring him 12 Giant Eggs, 10 Zesty Clam Meat and 20 Alterac Swiss. You should actually be able to buy the eggs and clam meat off of AH, but in case you can't here's where to find them. Now according to the quest Giant Eggs drop off of Rocs in Tanaris or any large bird. The best place I found for the eggs, was the owlbeast in The Hinterlands. Only needed to kill about 20 of these to get my 12 eggs. They are about level 43 ish, so if your not that high a level, get help or wait till you can handle them. The clam meat comes from clams, naturally! Well to save you swimming around the sea looking for clams, your better off killing turtles at Steamwheedle Port or Raventusk Village. The drop rate is quite high and you'll have your clam meat in no time. The levels are 41 ish for Steamwheedle Port and 49-50 for Raventusk Village. The Alterac Swiss is the easiest part. Go to the Inn in Goldshire, Elwynn Forest and buy them off of the Bartender. Hand them all in and you'll get your Artisan Cooking.

Second Quest: Fishing
Requirements: Level 35, 225 Fishing.

You need to go and find Nat Pagle in Dustwallow Marsh. He is standing on a small island to the West of Theramore (58,60). He'll ask you to catch four rare fishes for him. This quest is actually really easy and the only hard part is the amount of travelling involved.The fish you need to catch are:

Feralas Ahi - West from Camp Mojache. Fish the Verdantis River where the small bridge is by the Ogres, you'll soon catch one.

Sar'theris Striker - South or North or Shadowprey Village. Make sure the area comes up as Sar'theris Strand.

Savage Coast Blue Saffin - Just outside Grom'gol Base Camp. Make sure the area comes up as Savage Coast.

Misty Reed Mahi Mahi - Directly East from Stonnard. Just avoid the Murlocs.

You should catch these fish within 5 to 10 casts at each location. So it wont take long. I haven't done this quest on my Alliance character, so I'm not sure of the best order in which to do them.
Now go back to Nat and get your Artisan Fishing.

Go to Steamwheedle port and speak to Gikkix, You'll want to buy the following two recipes: Spotted Yellowtail and Poached Sunscale Salmon.
Either fish for Spotted Yellowtails at Steamwheedle Port or go to Raventusk Village (well not to it, just a little North of it) for the slightly better drop rate. You'll need about 30 to get your cooking from 225 to 250.
Now go to Bloodvenom Falls in Felwood and fish for Sunscale Salmon. You'll need about 30 to get your cooking from 250 to 275.
No go and speak to Vivianna in The Feathermoon Stronghold and buy the recipe for Mightfish Steak. Whilst your there buy about 40 Hot Spices and 40 Soothing Spices as your going to be making the food that you will want as a level 60 (without going into instances that is). It gives a +10 stamina buff for 15mins which is always helpful.
Now go to Scalebeard's Cave in Azshara (its one of the islands to the East) and fish for Mightfish. You'll need about 30 to get your cooking from 275 to 300. You may need to bring some lures with you at this point, as your cooking will level up faster than your fishing and Azshara is a 250+ fishing zone. Once your cooking is a 300, keep fishing till you've maxed out that too. It will take 7 to 10 catches to get one skill up at this point, so take your time.