Pal Park, Pal Park, and... hmm, Pal Park.
Although Feebas is obtainable in D/P even before the National Dex, if you have teeth-chattering patience enough to search for it.
XDD, I still laugh at how I found my Feebas in Sapphire... COMPLETELY BY ACCIDENT. XDDDD.
My little sister told me she found a Feebas by accident in Ruby a while back, after I went through the trouble of finding it myself in Emerald. "Oh, that's Feebas? I found that once...what's the big deal?" I learned after that that file had been saved over, but it didn't make me want to strangle her any less D:
Luck seems to go hand in hand with obliviousness more often than not.