Назва провулка дано за застарілим назвою скатертини - Столешников. виготовленням яких займалися жили тут з XVII століття ткачі.
Аж до 1922 року на місці нинішнього Столешникова провулок знаходилися два коротших: власне Столешников йшов від Петрівки до Великої Дмитрівки. провулок від Великої Дмитрівки до Тверської носив назву Космодаміанська. по церкви Косьми і Даміана в Шубіна.
Перша згадка про провулку (відомому тоді як Різдвяна вулиця) міститься в духовній грамоті Івана III 1504 року. Різдвяної вулицею провулок називався по церкви Різдва Богородиці, що в Столешніков. що стояла на розі з Петрівкою [1].
Ще в XVII столітті тут знаходилася реміснича слобода ткачів, «Столешніков», але в XVIII столітті в провулку вже стали розташовуватися двори знаті і чільних посадовців: князів Долгорукова. Трубецьких. Козловских.
Провулок був забудований тісняться впритул дерев'яними будинками, що таїло загрозу пожежі. Побоюючись вогню, князь Семен Мещерський. домоволодіння якого розташовувалося по сусідству з дворами церкви Воскресіння по Великій Дмитрівці. переніс дерев'яні будівлі на інший кут Столешникова провулка, а звільнений ділянку церковної землі взяв в довгострокову оренду [1].
Після пожежі 1812 року замість дерев'яних будинків в провулку були побудовані кам'яні (кілька таких невеликих кам'яних будинків, побудованих при церкві Воскресіння Словущого. І зараз стоять на розі Столешникова провулка і Великої Дмитрівки). У дворі князя Козловського, на розі з Великою Дмитрівка (будинок № 15), в першій половині XIX століття розміщувалася відома друкарня Селивановского.
У другій половині XIX і на початку XX століть в провулку стали переважати магазини і купецькі лавки. На пасхальному тижні в цих магазинах велася найцікавіша в місті «продаж залишків» від зимового сезону - залежалися тканини і галантерейні товари розпродавалися за зниженими цінами. В цей час в Столешниковом з'явилися нові 5-6-поверхові будинки з упорядкованими квартирами, в яких селилися особи вільних професій і торгові службовці з високими доходами [1].
У 1922 році Столешников провулок збільшили вдвічі, поширивши його назву і на Космодаміанська провулок під приводом того, що такий провулок в Москві вже є (одночасно були перейменовані Старосадскій і Старопанського провулки).
У 1930-х роках була знесена церква Різдва Пресвятої Богородиці в Столешніков. по якій провулок в старовину носив назву Різдвяної вулиці.
У 1970-х роках на місці будинку, де розміщувалася Тверська поліцейська частина, було зведений будинок Інституту марксизму-ленінізму. перед яким був розбитий сквер з фонтаном. На розі з Тверський вулицею. тоді називалася вулицею Горького, зросла багатоповерхове житлове будівля, повністю змінивши початок провулка [1].
Наш час
Чудові будівлі і споруди
За непарної сторони
За парній стороні
Магазини та установи провулка
Головне управління архітектури та містобудування Московської області; Головне управління державного будівельного нагляду Московської області, Фонд взаєморозуміння і примирення при Уряді РФ.
Також в провулку знаходяться різні бари і ресторани, туристичні агентства, адвокатські бюро та інші приватні організації.
Провулок в творах літератури і мистецтва
- У Столешниковом провулку багато років жив Володимир Гіляровський. який так написав про нього: «Столешников провулок! У ньому, як у краплі води сонечко, відбивається все життя міста ... ».
- Згадується в пісні Олександра Розенбаума. «А в Столешниковом - ну просто біда: цілий сонм спогадів і дум!»
- Цикл романів Василя Звягінцева «Одіссей покидає Ітаку»: квартира на третьому поверсі невідомого будинку - підпільна база інопланетян (аггро).
- Неодноразово згадується в 6-й серії серіалу «Слідство ведуть ЗнаТоКи»