Старое еврейское кладбище является первым известным местом захоронения евреев в Таллинне. История таллиннской еврейской общины восходит к средневековью, но в Новое время, в периоды шведского и российского владычества им было запрещено селиться на территориях Эстонии. Например, во время правления российской императрицы Екатерины Второй (1762–1796) евреям разрешалось жить только на ограниченных территориях современной Литвы, Беларуси, Украины и Польши, для выезда из которых евреям требовалось специальное разрешение. Еврейская община Таллинна оставалась малочисленной до решения российского царя Николая I в 1828 г., согласно которому воинская повинность стала обязательной и для евреев. После этого в Таллинн стали прибывать военнослужащие евреи, или кантонисты, многие из которых выбрали Таллинн местом жительства после окончания 25-летней военной службы. В 1845 г. было получено разрешение на строительство собственного кладбища рядом с Александро-Невским (Внутригородским) кладбищем на улице Магазини. До учреждения еврейского погребального братства Хевра Каддиша в 1856 г. здесь состоялись, вероятно, только одиночные похороны. Местная еврейская община стала более активно расти только при царе Александре II (1855–81), который ослабил ограничения, наложенные на евреев. В 1880-х годах в Таллинне насчитывалось около тысячи евреев – в 1880 году была построена начальная школа, а в 1884 г. на улице Маакри была достроена Большая хоральная синагога Таллинна, что стало очень важным событием для еврейской общины.
Для старого еврейского кладбища были характерны массивные каменные надгробия и места для погребения, окаймлённые кованой оградой, большинство умерших хоронили в саване, без гроба, по еврейскому обычаю. Списки похороненных на кладбище сохранились лишь частично. В 1880 г. архитектор Николай Тамм-старший спроектировал первое здание кладбища – привратный домик караульного. В 1910 г. на кладбище был открыт мавзолей Шайе Левиновича, основателя Таллиннской синагоги и лидера еврейской общины (архитектор Жак Розенбаум). Однако в том же году было принято решение о закрытии кладбища, так как кладбище располагалось в заболоченной местности, непригодной для захоронений, и исходивший от него смрад беспокоил жителей окрестностей. Однако последние похороны по специальному разрешению состоялись еще в 1936 г.
Старое еврейское кладбище было брутально ликвидировано по решению советских оккупационных властей в 1963 г. В 1967 году на месте кладбища были построены автобаза, ремонтная мастерская и автостоянка. Отходы сноса, в т. ч. надгробные плиты, были использованы при строительстве берегового укрепления между «Русалкой» и Старым портом, где часть их была обнаружена при строительстве дороги Рэйди в 2017 г. Привратный домик караульного был снесен в 1979 г. Идея восстановления кладбища исходила от отдела охраны памятников старины Таллиннского департамента городского планирования, который в 2019 г. заказал предварительные археологические исследования. Затем в сотрудничестве с городской управой Кесклинна, Городским советом, Эстонской еврейской общиной, Эстонской общиной иудейской веры и местными жителями был завершен проект реконструкции кладбища, который был реализован в начале 2020-х годов.