After going south from Mossdeep City and exploring Route 127 both above and underwater, go south to Route 128.
While Surfing, you might find Tentacool, Wingull, and Pelipper. With the Old Rod you can find Tentacool and Magikarp, with the Good Rod you can find Magikarp, Wailmer, and Luvdisc, and with the Super Rod you can find Luvdisc, Corsola, and Wailmer.
Explore the Route
There are three hidden Heart Scales on the shallow water areas of this route. There is also a Protein and a Pearl hidden in rocks in this route.
On the islands here, you can find Cooltrainer Ruben, who has Shiftry, and in Ruby and Sapphire has Graveler, and Loudred, or in Emerald has Nosepass; Cooltrainer Alexa, who has Gloom and Azumarill; Fisherman Wayne who has Tentacool, Wailmer, and (Ruby Sapphire only) Tentacruel; Triathlete Isaiah, who has Staryu; Triathlete Katelyn, who has Staryu; and in Emerald only, Swimmer Carlee who has Seaking and Swimmer Harrison who has Tentacruel. The swimmers might team up for a Double Battle.
Ever Grande City is to the east, but you can't access it yet.
When you are done exploring, go to the middle of the route where there is a ring of shallow water with rocks around it. Go to the dark water south of the southernmost rock and use Dive. Then go into the cave and swim up to the submarine, then go to the surface to reach the Seafloor Cavern.