Марк Рудинштейн родился в еврейской семье 7 апреля 1946 года в Одессе. Родители Марка Рудинштейна: Тауба Исааковна и Израиль Григорьевич. Трудовую деятельность начал в 15 лет на судостроительном заводе в Николаеве. После — служил в армии.
Учился в ГИТИСе (не окончил), затем в 1972—1976 годах учился на очно-заочном отделении в Театральном училище им. Б. Щукина (мастерская М. Тер-Захаровой).
В период с 1982 по 1987 годы Рудинштейн находился либо в тюрьме, либо под следствием. Был осуждён за «дачу взяток» и «расхищение социалистической собственности» на 6 лет, отсидел 11 месяцев, после чего был оправдан. В период с 1982 по 1983 года был директором и организатором концертов ВИА «Здравствуй, песня!»
Был организатором первого в СССР рок-фестиваля, прошедшего в Подольске в «Зелёной эстраде» в сентябре 1987 года.
В 1989—1991 годах генеральный директор кинодистрибюторской фирмы «Подмосковье».
В 1994 году Марк Рудинштейн пытался воссоздать кинофестиваль «Золотой Дюк».
В интервью 2002 года украинскому театроведу Натальи Влащенко рассказал о конфликте с Никитой Михалковым.
В начале 2010 года выступил с мемуарами, в которых откровенно разоблачил нравы отечественной кинобогемы, после чего стал героем ряда телепередач, посвящённых мемуаристике, причём запись передачи «Пусть говорят» в эфир не вышла .
Состоит в третьем браке.
Имеет дочь Наталью от первого брака.