Название переулка дано по столешникам: так в старину назывались скатерти, которые изготовляли для царского двора ткачи, обитавшие здесь в XVII веке.
    Первое упоминание о переулке (известном тогда как Рождественская улица) содержится в духовной грамоте Ивана III 1504 года. Рождественской улицей переулок тогда назывался по церкви Рождества богородицы, что в Столешниках (стояла на углу улицы Петровки, снесена в 1930-е годы).
    Во второй половине XIX и в начале XX веков в переулке стали преобладать магазины и купеческие лавки. На пасхальной неделе в этих магазинах велась самая интересная в городе «продажа остатков» от зимнего сезона. Залежавшиеся ткани и галантерейные товары распродавались по сниженным ценам. В это время в Столешниковом появились новые 5-6-этажные доходные дома с благоустроенными квартирами, в которых поселилось много лиц свободных профессий и торговых служащих с высокими доходами.
    В первые годы после Октябрьской революции все торговые помещения Столешникова переулка стали складами, но со временем в них снова открылись магазины.