To catch a legendary fish, you don't need to be any level but since of a update, buy legendary lures, and rent a fishing boat. Despite the stories told by fishing masters, all legendary fish can be found anywhere on the map.
Once on a fishing boat, put a Legendary Lure on your line and make sure it sinks as far as it can go. The skill "Sink Lure" is useful for this. If you don't see vegetation at the bottom of the screen, you are not deep enough. Once near the bottom, wait for a while. Make sure you scare away any fish that come near. It could take up to 10 minutes of waiting, but a legendary fish should eventually appear.
Once a legendary fish takes the bait, you will have to do a little minigame to reel it in. This works in three phases: Struggle, Reel and Catch. The game will usually alternate between "reel" and "struggle", with an occasional "catch".