Свою сучасну назву вулиця дістала 5 липня 1841 року, завдяки маєтку одеського міщанина Дементія М'ясоїда. Дементій М'ясоїд володів на вулиці також пивним і квасовим заводом. Так, існує документ від 2 лютого 1835 року «о покупке имения, принадлежащего одесскому мещанину Дементию Мясоедову, заключающегося в пивном и квасном заводе с принадлежащими оному пристройками, состоящего в IV части, — предместье Молдаванка». Маєток М'ясоїда (також вказується як М'ясоєдов) будував Нікіфор Черкунов, тодішній відомий городовий архітектор IV частини міста. Точне розташування цього маєтку невідоме, однак 3 березня 1853 року вказується, що «Дом Мясоедова на Молдаванке, Тираспольская улица у Черепенникова моста». Черепенніков міст через Порто-Франківський рів знаходився на місці сучасного Прохоровського скверу навпроти вул. Великої Арнаутської, тобто не на Мясоїдівський, а скоріш на Прохоровській.
Історія вулиці тісно пов'язана із створенням Єврейської лікарні (тепер — Міська клінічна лікарня № 1). Наприкінці 18-го століття в Одесі існувало єврейське Товариство навідування хворих — «Бікур Холим». Розширюючи свою діяльність товариство створило у 1802 році лікарню (Хекдеш) на 6 ліжок, яка розміщувалася у Карантинній балці. Вже за рік існування лікарня розширилася до 20 ліжок. У 1829 році лікарня купила маєток на Молдаванці. Тут розмістили 60 ліжок, а штат складався із лікаря, цирульника, кухарки, прачки, двірника і декількох служителів. Маєток, де було розміщено лікарню, знаходився саме на перетині сучасних вулиць М'ясоїдівської і Богдана Хмельницького, яка тоді дістала назву Шпитальної. У 1866 році частина вулиці М'ясоїдівської, від Прохоровської до Болгарської, змінила назву на Єврейсько-Лікарняна, завдяки Єврейській лікарні, що знаходилася тут на перехресті із Шпитальною вулицею. У 1870 році цю саму ділянку перейменовують на Шпитальний провулок, але на практиці назва М'ясоїдівська використовуються для усієї вулиці від Трикутної площі і до Болгарської (вулиці Мечникова тоді не існувало, на її місці вздовж стіни цвинтаря проходила правобічна забудова Старопортофранківської вулиці).
У 1928 році назву вулиці змінено. Тепер її назвали в честь відомого єврейського письменника Шолом-Алейхема, який мешкав на цій вулиці з 1860 року.
Історичну назву М'ясоїдівська вулиця було повернено в період з 19 листопада 1941 року до 14 квітня 1944 року, після чого радянська влада знову її змінила. Остаточне повернення історичної назви відбулося тільки 15 травня 1995 року.