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

Переулок назван по находившейся здесь слободе.

Каменных дел мастера – каменщики-строители – всегда были в Москве людьми уважаемыми, их трудом Москва приобрела светлый и праздничный эпитет – белокаменная. Слободы каменщиков находились в разных частях города: на Таганке, в Лефортове. Одна из самых старых слобод была на Арбате, у Смоленского рынка.

Переулки Каменной слободы в XVIII веке переменили несколько названий. Тот, который называется Каменная Слобода, назывался Рещиковым и Малым Толстовским по домовладельцам. В 1965 году он переименован в переулок Воеводина. П.В. Воеводин (1884—1964) – старый большевик, член ВЦИКа, после революции занимал ответственные хозяйственные посты, работал редактором. Последние годы жизни проживал поблизости – на Новинском бульваре.

При возвращении исторического названия переулку из всех его прежних названий было выбрано самое раннее.