Feebas can only be found in one area which is Route 119, the place where you have to rescue the people from the weather institute from Team Magma/Aqua. If you’ve ever looked around on this route, you’ll see that along with the high grass, many secret base locations, and pouring rain, there’s a lot of water. This is where you can find Feebas. Here’s the catch though: he will only appear on six of the hundreds of tiles on that route. Yes. Six. Any rod will do, meaning you can use ANY rod, however its better to use a Super Rod as the only Pokémon you can get with that apart from Feebas is Carvanha, but patience is required if you want to catch this thing. Like in actual fishing in real life.
Now, if you get annoyed and feel like shuffling the spots where the Feebas are, all you need to do is change the trendy phrase in Dewford. No, it doesn’t make sense how a trend on an island that’s nowhere near the Feebas affects them. Bear in mind that they don’t take assigned spots with the trendy phrase, so if you and your friend have the same phrase and one of you finds Feebas in one location, chances are that the other person won’t find Feebas in that location.
Now, when you’re looking for Feebas, make sure you search every single tile a few times. Like 5, or something. On the tiles that it actually appears on, it’s actually pretty common. So, if you fish a tile that it appears on a few times, chances are that you’ll find the thing. Also, make some sort of pattern across the water surface. Here’s a simple diagram with nothing but text arrows telling you what I mean:
Quoted from Serebii.