В том месте, где в последующем был возведён этот мост, ранее был брод, являющийся частью дороги, называемой Волоцкая, которая шла через Волок Ламский, соединяя Рязань и Новгород. В 1643 царь Михаил Фёдорович издал Указ, согласно которому Страсбургский мастер Ягон Кристлер начал строительство этого моста, который стал первым постоянным каменным мостом через Москву-реку, находившимся у Всехсвятских ворот.
Когда Михаил Фёдорович скончался, строительство моста было остановлено, поскольку его проект посчитали слишком дорогим и смелым. Работы по проекту Кристлера возобновились только в 1682—1687 годах. Их инициаторами стали царевна Софья и князь Василий Голицын.
Мост был достроен в 1692 году и получил название Всехсвятского, но с течением времени его стали называть Большим каменным мостом. Это название сохранилось и до наших дней.
Мост состоял из 8 арок, через средние пролёты, ширина которых составляла 15 м, проходили лодки и плоты. Общая длина моста была 170 м, его ширина - 22 м. На замоскворецкой стороне перед мостом была возведена предмостная Шестивратная башня.
Строительство этого моста оказалось настолько дорогим, что по Москве в те времена стала ходить поговорка "Дороже Каменного моста!", смысл которой был подчеркнуть дороговизну или ценность чего-то. И она не утратила своей актуальности в течение почти полутора веков. А в Нижнем Новгороде в девятнадцатом веке появилась поговорка «Каменного моста лучше!».
Поскольку мост был шире практически в 3-4 раза даже самых широких улиц Москвы, его застроили с обеих сторон. Во времена правления Петра I на этом мосту располагались табачная таможня, каменные палатки Князя Меньшикова (всего четыре штуки), палата Предтечевского монастыря и пивной двор.
А территория под мостом стала местом сборищ «лихих людишек». Самой дурной славой в этом смысле пользовался левобережный пролёт, так называемая «девятая клеть». Это место москвичи всегда старались обходить стороной.
Во время весеннего наводнения 1783 года мост был сильно повреждён, а спустя три года стихийное бедствие повторилось. Главнокомандующий граф Брюст отдал приказ реконструировать и отремонтировать мост, что и было сделано.
В пятидесятые годы девятнадцатого века мост настолько обветшал, что было принято решение снести его. И только в 1938 году был построен тот мост, который и дошёл до наших дней. Автором его стал инженер Н.Я.Калмыков. Правда, место возведения для моста было выбрано немного ниже по течению, так как иначе к нему было трудно подъехать из-за узости Ленивки.
Современный мост вместе с подъездами имеет в длину 487 м, при этом речной пролёт составляет 105 м, береговые — 42,5 м. Ширина моста - 40 м. С Большого Каменного Моста открывается вид на Храм Христа Спасителя, Дом на набережной, Софийскую, Пречистенскую и Берсенёвскую набережные и, конечно, на Кремль.