On Route 119, but it has a very strange method of appearance.
Feebas are elusive along Route 119. Instead of being found in any fishing location as would be customary with most Pokémon, Feebas are located in only six random water blocks along the route. Adding to the difficulty, other Pokémon besides Feebas will still appear in the Feebas blocks as well. There is no known easy method to determine which blocks contain Feebas: the only way is fish repeatedly into each and every water block on the route, doing so enough times to be reasonably confident that no Feebas are in that block (or else just risk missing a block). Any rod can find Feebas. Once hooked, a Feebas is an easy catch, and they can be fished from the same tile many times.
The probability of finding a water tile with Feebas on Route 119 is 1/72.66666..., with six possible fishing spots on 436 water tiles.
So you must fish in the right tiles to find it. They are relatively common if you fish in the correct tile, so try fishing in lots of different spots. It has a 0% chance of appearing on the incorrect tile; so you're going to have to keep looking...