В 1878 году на берегу реки Фонтанки напротив Лештукова переулка (ныне переулок Джамбула) было построено здание Суворинского театра (ныне Большой Драматический Театр). Это заведение стало популярным, рядом с ним через Фонтанку был организован лодочный перевоз.
Перед началом реставрации Чернышёва моста здесь было решено построить временную переправу. Деревянный пятипролётный мост был построен за весну и лето 1907 года, на что было потрачено 33 270 рублей и 80 копеек. Переправу назвали Лештуковым мостом. Своё имя он взял от Лештукова переулка, который в свою очередь так назывался по находившейся рядом усадьбе, принадлежавшей ранее лейб-медику императрицы Елизаветы Петровны англичанину Лестоку. Первоначально переулок являлся внутридворовым проездом усадьбы Лестока.
Временный мост просуществовал гораздо дольше первоначально отведённых ему сроков. В конце концов в начале 1930-х годов он сгорел. В 1934 году на этом же месте мост был восстановлен. В 1953 году деревянные балки Лештукова моста заменили металлическими, установили металлические перила, расширили въезд на мост, опоры обшили "под камень". Первоначально по Лештукову мосту могли ехать машины. Но уже к концу 1950-х годов деревянные перекрытия прогнили, из-за чего переправа стала пешеходной.
В 1988 году инженером Л. Н. Соболевым был разработан проект реконструкции Лештукова моста. Соответствующие работы были проведены в 1995-1997 годах. Лештуков мост стал в два раза шире (ширину увеличили с 14 до 28 метров), по нему вновь было открыто транспортное движение. Конструкция моста оказалась настолько удачной, что появилась идея организовать на нём автомобильную стоянку. Транспортный поток предлагается пустить по новому мосту, который мог бы быть построен рядом, в створе Бородинской улицы
В петербургском фольклоре существует фраза, связанная с Лештуковым мостом - "Нет ли лишнего билетика?". Такая фраза закрепилась за ним благодаря популярности находящегося рядом театра.
