Название XVIII века.

Переулок назван по домовладельцу.

Алексей Яковлевич Милютин – колоритная фигура Петровской эпохи. Его дед был слугой при дворе царя Михаила Федоровича, отец занялся предпринимательством: будучи у государевых рыбных промыслов, поставлял рыбу из Астрахани и Нижнего Новгорода к царскому двору. Сам же Алексей Яковлевич в своей деятельности соединил службу при дворе и купеческие операции.

При Петре I и его наследниках он служил комнатным истопником, одновременно в 1714 году завел в Москве шелковую мануфактуру. Милютин приобрел землю между Мясницкой и Сретенкой, где прежде был Казенный полковой двор Семеновского полка, переведенного в Петербург, выстроил обширное каменное здание для фабрики, поставил вокруг своих владений каменную ограду, а когда в 1721 году разрешили купцам-заводчикам покупать села с крестьянами, одним из первых воспользовался этим.

В 1740 году А.Я. Милютин, продолжавший служить комнатным истопником при дворе, был пожалован императрицей Анной Иоанновной грамотою на дворянство с гербом. Мануфактура Милютина оставалась крупнейшей в Москве в течение всего XVIII века.

Переулок был назван Милютинским в начале XVIII века, прежде он назывался Казенной улицей или Старым Казенным переулком по полковому двору.

До настоящего времени в переулке сохранились дома А.Я. Милютина, по нынешней нумерации – 14 и 16.

В 1927 году Милютинский переулок переименован в улицу Мархлевского. Ю. Мархлевский (1866—1925) – польский коммунист, деятель международного рабочего движения; живя с 1918 года в Москве, Мархлевский часто выступал в клубе польских коммунистов-эмигрантов, помещавшемся тогда в этом переулке в доме 16.