The story
The Padma Purāṇa tells of a demon named Mura who hid inside Viṣṇu while he slept, and of a maiden born from the sleeping god's body who killed him. Viṣṇu woke, named her Ekādaśī after the day, and granted that whoever keeps her day is freed from what they have done.
The fast is older than the story. Grain is what the body reaches for first, and setting it aside for a day is the smallest renunciation a householder can make without leaving the house — which is the point of a vrata as against a retreat.
Each of the twenty-four has its own name and its own telling, and the almanac names them: Vaikuṇṭha Ekādaśī in Dhanurmāsa is the largest, Nirjalā in Jyeṣṭha the hardest, and the two that fall in an intercalary month are Padminī and Paramā.