Таку назву вона отримала від храму Пресвятої Трійці, що розташований в її самісінькому центрі. У плані церква схожа на листок конюшини. Такі сакральні споруди називають триконховими. Уперше Троїцька церква згадується у документах 1535 р., а за археологічними дослідженнями датується ХV ст. Упродовж XVI-XVII ст. вона була головним православним храмом міста. У цей період при ній існувало одне з найдавніших на території України братств – Свято-Троїцьке. Після захоплення міста турками, святиню перетворили на мечеть Мустафи-паші й прибудували до неї мінарет. На початку XVIII ст. тут облаштували греко-католицьку церкву.
У XVIII ст. єпископ Атанасій Шептицький передав храм монахам чину св. Василя Великого, які заснували при ньому монастир. Саме в цей період Свято-Троїцькому храму було підпорядковано всі монастирі Подільського воєводства. При монастирі відкрили школу богослов’я для 12-15 осіб, які бажали стати монахами. У 1795 р. монастир перетворили на православний. З 1806 р. його настоятелі одночасно були ректорами Подільської духовної семінарії. У буремному ХХ ст. храм спіткала трагічна доля: 1935 р. в ході антирелігійної кампанії його зруйнували більшовики. Відновили церкву лише в 2005-2010 рр.