Li first met Naija some time before the events of the game when she was exploring the Veil. He was so surprised to see a green-skinned girl pop up from the water. She waved at him and disappeared beneath the waves once more.
After his close encounter with the girl from beneath the ocean, he set out on an expedition. Readying supplies and a deep-sea submersible, he headed underwater to find her.
He spent an unknown amount of time in the waters of Aquaria, searching for Naija. In the end, it was she who found him. She thought his breathing apparatus to be some kind of strange binding around his face. Using the Bind Song, she yanked the helmet off his head, and he began to drown.
As though moved by some unknown force, she moved in close and pressed her face to his, and the notes of the Verse flowed down his throat into his body. Naija passed out after this, but Li did not drown. He found himself able to breathe the water as easily as he did air. Furthermore, he found his digestion and tastes had changed as well. He could eat raw fish to no ill effect.