Сын торговца зерном, он в юности работал в иконописной мастерской, а с 1909 года учился в Одесском художественном училище. В 1916 году, после смерти матери, поступил в Московское училище живописи, ваяния и зодчества, которое затем было преобразовано в ВХУТЕМАС. Там он учился у Давида Штеренберга и Владимира Татлина, под влиянием которого стал близок к конструктивизму.
Во время учебы познакомился с Владимиром Маяковским, с которым стал дружен, и вместе создавал искусство плаката. В 1922 году вместе с поэтом выехал в Берлин, но из-за границы не вернулся. Видимо из-за этого, на долгие годы был вычеркнут из истории российского искусства.
В 1923 провел первую персональную выставку в Лодзи (Польша), откуда родом была его жена - Базия. В том же году приехал с ней в Париж, поселяется в Médical Hôtel на улице Сан-Жак, и вскоре вливается в интернациональный круг художников, который назовут «École de Paris» — Парижской Школой. Он посещает кафе и мастерские в районе Монпарнас на юге Парижа, в частности знаменитый «Улей» — «La Ruche». Там он встречается с товарищами: Жаком Шапиро, Осипом Любичем, Лазарем Воловиком, Мишелем Кикоиным, Пинхусом Кремнем и др.
Творчество Марка Стерлинга отличалось большим разнообразием, он не ограничивался одной манерой, постоянно меняясь и экспериментируя. Он работал в разных техниках: масло, гуашь, рисунок, тушь, гравюра. Писал портреты, жанровые сцены и натюрморты.
В первые годы в Париже, общаясь с такими художниками, как Пикассо, Хуан Грис, Жорж Брак, Метцингер, он работает в стиле синтетического кубизма. В течение 1930-х годов, стиль Стерлинга становится более пластичным и лирическим — букеты цветов, клетки с птицами, портреты дочерей, выполненные в реалистичной манере.
Во время Второй мировой войны Стерлингу с семьёй удаётся избежать нацистских преследований, скрываясь у друзей во французской провинции. По окончании войны, он постепенно возвращается к нормальной жизни и работе. Однако послевоенные произведения несут на себе печать трагедии — это тёмные кошмарные видения.
Потеряв жену, которая скончалась во время операции в 1941 году, Стерлинг женится вновь на молодом скульпторе из Швейцарии — Элиан, ученице Осипа Цадкина. В 1947 он вернулся в Париж и получил французское гражданство. С начала 1950-х годов появляются новые цвета и новые сюжеты полные покоя и нежности — обнажённые, портреты. Он также обращается к еврейской тематике.
В 1953–1956 живет в Peseux в Швейцарии, после чего вновь возвращается в Париж. Путешествовал по Италии, Испании, Голландии и Израилю.
В последний период, 1960—1970-е годы, появляется всё больше свободы в красках, а также в сюжетах: фантастические существа, сказочные животные, воображаемые пейзажи, близкие к сюрреализму.
Несмотря на наступающую слепоту, он продолжает работать до своей смерти 7 сентября 1976 года.
Персональные выставки художника прошли в галереях: Bernheim (1928), Zak (1929 – совместно с В. С. Бартом; 1937), Billiet–Worms (1934), J.Rotgé (1936), des Garets (1950), Conti (1952), Bassano (1954) и др. Выставлялся в салоне Тюильри (1923, 1932) и Осеннем салоне (1928, 1949, 1951). Участвовал в выставках русских художников в кафе «La Rotonde» (1925), в галереях Сhez Fast (1927/1928), d’Alignan (1931) и Zak (выставка журнала «Наш Союз», 1936), в выставке «Современные русские художники и скульпторы», организованной комитетом «Франция–СССР» XIV округа Парижа (1945), и «Русские художники Парижской школы» в Доме французской мысли (1961), а также в выставке «Русские художники-эмигранты в Париже» в лондонской галерее Redfern (1953).
Работы Стерлинга вошли в альбом «Art Russe moderne» (1928), экспонировались на выставке группы «Новый рисунок» в нью-йоркской галерее Аrtists (1947), воспроизводились во французских, немецких и итальянских журналах.
В 1972 году в связи с 75-летием со дня рождения художника в галерее Motte в Париже состоялась ретроспективная выставка. В 1978 году его ретроспектива прошла в Нёвшателе (Швейцария).
Произведения художника находятся в Национальном Музее Современного Искусства — Центре Помпиду (Париж), Муниципальном Фонде Современного Искусства Парижа, Музее Тель-Авива, Национальной Библиотеке Франции, в частных собраниях.
