Padberg grew up in Zagreb, Croatia, and Westphalia. From 1961 he studied mathematics at the University of Münster, where he graduated in 1967. In 1967, he was a research assistant at the University of Mannheim. Starting in September 1968, he studied at Carnegie Mellon University, where he obtained a master's degree and his Ph.D. (1971) in Industrial Administration. His advisor was Egon Balas and his dissertation was titled Essays in Integer Programming.
Afterwards he worked from 1971 to 1974 at the Berlin Science Center. From 1974, he was Associate Professor and, from 1978, Professor of Operations Research at New York University. He became a professor emeritus in 2002. He moved to Paris in 2002.