Древне еврейская синагога помещается на возвышении у подошвы холмов, окружающих Феодосию.
Среди местных евреев сохранилось сказание, что синагога в древности была найдена разрушенной и засыпанной землей, затем была отрыта и реставрирована. Профессор Хвольсон, на основании переводов древних надписей синагоги, утверждает, что построена она в 909 году, а реставрирована в 1309 году.
В синагоге сохранился ряд древних надписей, вделанных в стены. Сохранился чрезвычайно интересный портал, высеченный из громадной известковой плиты, украшенный типичной Сельджукской плетенкой. Сохранились в синагоге 2 мраморных колонны, две других, по преданию, перенесены в одну из каффских церквей. В настоящее время ни в одной из церквей нет подобных колонн.
Долгое время среди феодосийских евреев и караимов шел спор за обладание синагогой. Караимы пытались доказать, что это не синагога, а кенасса, но миква (род купели), найденная в синагоге, решила спор в пользу евреев.
Неподалеку от синагоги находится караимская кенасса, по преданию построенная на древних фундаментах.