Родился 7 февраля 1926 г. в Харькове (Украинская ССР, ныне Украина). Отец был инженером, мать имела музыкальное образование. Спустя полгода после рождения ребенка семья переехала в Ленинград (Санкт-Петербург). Марк Тайманов с детства занимался музыкой. Он увлекся шахматами только в 11 лет, когда начал посещать шахматную секцию при ленинградском Дворце пионеров им. А.А. Жданова.
В 1934 г. Марк Тайманов поступил в музыкальную школу при ленинградской Капелле по классу фортепиано, впоследствии учился в школе-десятилетке при Ленинградской консерватории (ныне - Санкт-Петербургская государственная консерватория им. Н.А. Римского-Корсакова). В 1936 г. исполнил главную роль - музыкально одаренного мальчика - в фильме Владимира Шмидтгофа и Михаила Гавронского "Концерт Бетховена".
Во время блокады 1941-1944 г. он вместе с матерью находился в эвакуации в Ташкенте (ныне - Узбекистан). После окончания Ленинградской консерватории по классу фортепиано выступал с фортепианными концертами вместе со своей первой женой Любовью Брук. Записал несколько пластинок.
Кроме занятий музыкой принимал участие в шахматном кружке Консерватории. Стал пятикратным чемпионом Ленинграда (1948, 1950, 1952, 1961, 1973), в составе команды города шесть раз выступал на Спартакиадах народов СССР.
В 1952 г. Марк Тайманов получил звание международного гроссмейстера.
Более 20 раз принимал участие в первенстве Советского Союза по шахматам. В 1956 г. стал чемпионом страны, опередив в дополнительном турнире призеров Юрия Авербаха и Бориса Спасского.
Тайманов дважды участвовал в соревнованиях претендентов на матч с чемпионом мира. В 1953 г. занял 3-7 место в турнирной таблице; в 1971 г. в четвертьфинале матчей претендентов проиграл будущему чемпиону мира американцу Роберту Фишеру со счетом 0:6.
В 1976 г. в составе команды "Буревестник" стал победителем Кубка европейских клубов.
В общей сложности Марк Тайманов являлся победителем и призером более 40 крупных международных турниров.
Был известен как шахматный теоретик, изучал теорию дебютов (сицилианская защита, испанская партия, защита Нимцовича). Занимался журналистикой; с 1983 г. был шахматным обозревателем журнала "Огонек".
Скончался 28 ноября 2016 г. в Санкт-Петербурге в возрасте 90 лет.
Был удостоен ордена Почета (1996) и медали "За трудовую доблесть" (1957).
Был женат четыре раза, имел семерых детей.