The Madness Monster has presumably always existed inside Warlock's mind. It has described itself as the sum of all of Adam's worst impulses, those things that he keeps most suppressed. The Madness Monster lurked within the "Door of Madness" inside Warlock's mind, which was part of the twisted "clown world" he experienced due to the Matriarch's brainwashing technology.
Adam Warlock had been captured by the Matriarch of the Universal Church of Truth, who attempted to brainwash him. The Matriarch hoped that if she could control Adam, his future self and her master, the Magus, would be forced to bend to her will.
The Matriarch had two of her technicians, Len Teans and Jan Hatroomi (that's Stan Lee and John Romita scrambled folks) attempt to brainwash Adam by drugging him and placing a VR-type helmet on his head. However, Adam's incredibly strong will turned the brainwashing program into a tableau of clowns. Quickly tiring of the clowns' shenanigans, Adam bullied Teans into showing him the only way out, which was through the Door of Madness. Adam boldly kicked the door open, only to be immediately accosted by the Madness Monster. Adam found the Monster so repulsive that he broke his own taboo and attempted to steal the Monster's soul. However, the gem had no effect. The Monster revealed that it had no soul, it was merely the manifestation of Warlock's worst impulses! In fact, the Madness Monster is the part of Warlock's mind that created the Magus. The two began to grapple and debate, with the Monster winning both contests. Finally, he talked Warlock into surrendering to him by convincing him that the Monster was not really evil, merely a different point of view.
In his subsequent battle with the Magus, Warlock learned that the Magus had planned for him to submit to madness all along. Madness was only the first step in transforming Adam's mind into the Magus'. The encounter with the Monster helped Adam access certain extrasensory powers that he would only fully realize as the Magus.