You must catch a Feebas in Mt. Coronet. If you enter through the Hearthome City side, and head toward Snowpoint City using the cave, there should be a lake that looks like this:
Out of all the spots on the lake, there is only 4 spots in the entire lake where Feebas can be found, using the Old Rod. You must check every square. More than once, as Magikarp can also appear. After you catch it, feed it many Dry Poffins, which raises its beauty. When Feebas' beauty is maxed out, it should similar to:
Not exactly like that, be that's the only picture I could find, as it is from Gen III. That green part should hit the beauty. Then, Level it up.
You got a Milotic :D