Родился 7 апреля 1946 г. в Одессе (Украинская ССР, ныне Украина).
С 15 лет работал судосборщиком на заводе в Николаеве (Украинская ССР). В середине 1960-х гг. был призван в Советскую армию, служил в одной из подмосковных частей ПВО.
В 1972-1975 гг. учился на актерско-режиссерском отделении Театрального училища им. Б. В. Щукина (ныне Театральный институт им. Бориса Щукина при Государственном академическом театре им. Евгения Вахтангова). Был студентом мастерской педагога Марианны Тер-Захаровой, диплом об окончании вуза не получил. В 2011 г. в интервью казахстанской газете "Литер" Марк Рудинштейн сообщил, что "семь лет назад защитил диплом по специальности "менеджмент организации". В 2016 г. в интервью изданию "Еврейский журнал" упоминал, что в 1992 г. заочно получил высшее образование по специальности "организатор концертной деятельности".
Административная деятельность
Во второй половине 1970-х - 1980-х гг. в разное время Марк Рудинштейн работал администратором в парках подмосковного Подольска, а также директором эстрадных программ Государственного концертно-гастрольного объединения РСФСР (Росконцерт). В 1986 г. после длительного следствия был осужден на шесть лет по уголовному делу о хищении (касалось периода его работы в Росконцерте). Пробыл в заключении 11 месяцев, после чего был оправдан.
В 1987-1988 гг. Марк Рудинштейн занимался организацией рок-фестивалей в Подольске.
В 1989-1991 гг. был генеральным директором компании "Подмосковье" и одноименного центра досуга (Подольск).
Работа в кино, предпринимательская деятельность
В апреле 1990 г. Марк Рудинштейн вместе с компанией "Подмосковье" провел в Подольске "Фестиваль некупленного кино". Мероприятие было призвано поддержать советские картины, не попавшие в прокат из-за конкуренции с зарубежными фильмами.
В мае 1991 г. в Сочи (Краснодарский край) прошел I Всесоюзный кинофестиваль "Кинотавр", организатором которого выступило творческое объединение "Подмосковье" при участии журнала "Экран", газеты "Дом кино" и Союза кинематографистов СССР.
С 1991 по 1999 г. Марк Рудинштейн являлся президентом кинокомпании "Кинотавр" и генеральным продюсером одноименного фестиваля, с 1999 по 2005 г. - президентом группы компаний "Кинотавр". В 2005 г. передал права на проведение "Кинотавра" Александру Роднянскому (впоследствии - президент фестиваля; в 2022 г. признан в РФ иноагентом) и Игорю Толстунову (в 2005-2010 гг. являлся генеральным продюсером фестиваля). В том же году стал учредителем компании "Киномарк" (работает в сфере производства фильмов и телепрограмм).
С 2001 г. по инициативе Марка Рудинштейна проводится Международный детский фестиваль искусств "Кинотаврик" (в разные годы проходил в Сочи и Москве).
Участвовал в продюсировании более десяти фильмов. В их числе: "Гамбринус" по мотивам рассказа Александра Куприна (1990, режиссер Дмитрий Месхиев), "Самоубийца" по мотивам пьесы Николая Эрдмана (1990, Валерий Пендраковский), "Циники" (1991, Дмитрий Месхиев), "Короткое дыхание любви" (1992, Валерий Харченко), "Аномалия" по мотивам рассказа Клиффорда Саймака "Все живое - трава" (1993, Юрий Елхов).
В качестве актера снимался в нескольких десятках фильмов и сериалов. Среди них: "Приходи на меня посмотреть" по мотивам пьесы Надежды Птушкиной "Пока она умирала" (2000, Михаил Агранович и Олег Янковский), "Курортный роман" (2001, Александр Павловский и др.), "Летний дождь" (2002, Александр Атанесян), "Московская сага" по роману Василия Аксенова (2004, Дмитрий Барщевский), "Мне не больно" (2005, Алексей Балабанов), "Вольф Мессинг: видевший сквозь время" (2009, Владимир Краснопольский и Валерий Усков), "Торгсин" (2017, Дмитрий Петрунь).
Являлся членом Российской академии кинематографических искусств, Национальной академии кинематографических искусств и наук России.
Был соучредителем негосударственного образовательного учреждения дополнительного образования "Хореографическая школа "Фантазия" (Подольск).
Звания, награды
Заслуженный работник культуры РФ (2003).
Обладатель спецприза "За выдающийся вклад в российскую киноиндустрию" фестиваля "Кинотавр" (2009).
В 2011 г. Марк Рудинштейн был удостоен премии "Золотой носорог" (вручалась в области сериального производства) в категории "Лучший актер второго плана" ("Вольф Мессинг: видевший сквозь время").
Кончина
Марк Рудинштейн скончался 5 декабря 2021 г. в Москве на 76-м году жизни.