Malzberg originated from a Jewish family and graduated from Syracuse University in 1960. He worked as an investigator for the New York City Department of Welfare in 1961–1962 and 1963–1964. In 1963, he was employed as a reimbursement agent for the New York State Department of Mental Health. He married Joyce Zelnick in 1964.

His first published story was "The Bed" under the pseudonym "Nathan Herbert" in the men's magazine Wildcat. His first science fiction story ("We're Coming Through the Window") was published in the August 1967 issue of Galaxy. Malzberg frequently repurposed existing stories for his science fiction sales. He first found commercial and critical success with publication of his surreal novelette "Final War" in The Magazine of Fantasy and Science Fiction under the name K. M. O'Donnell in 1968.

He had been writing erotic novels using the pseudonym "Mel Johnson" but began writing erotic novels under his own name in 1968 for Maurice Girodias's Olympia Press.

Many of his science short stories and novels in the late 1960s were published under the pseudonym "K. M. O'Donnell", derived from the surnames of Henry Kuttner, C. L. Moore, and their joint pseudonym "Lawrence O'Donnell.

For years, Malzberg has collaborated with friend and fellow science fiction writer Mike Resnick on a series of more than 50 advice columns for writers in the Science Fiction and Fantasy Writers of America's quarterly magazine SFWA Bulletin.