Храм впервые мупоминается в 1750 г., где проживает 257 прихожан.[1]

Цей храм був дерев’яний і коли виникла потреба або робити капітальний ремонт, або будувати новий, більш просторий, то був збудований кам’яний храм у 1800 р., котрий освячений, як і попередній, на честь святої Трійці.[2] Новая церковь была построена благодаря средствам и усердию помещика коллежского асессора Апполинария Львовича Шагарова.[3]

В Мезеновке была экономия и усадьба рода баронов фон Раденов, приобретенная ими в первой половине XIX ст. Род этот происходит из балтийских немцев, принявших православие и служивших по большей части в российской кавалерии. Последним владельцем имения в Мезеновке был действительный статский советник, предводитель дворянства Ахтырского уезда барон Михаил Павлович фон Раден. Он вышел в отставку из военной службы в 1860-е годы и посвятил свою дальнейшую жизнь благоустройству Ахтырского уезда, главным образом избираясь в земские учреждения. Он был одним из главных жертвователей на Троицкий храм в Мезеновке, и ему было дозволено при храме устроить семейный склеп. В 1887 г. в этом склепе была похоронена его первая жена Марта Ивановна, а в 1901 г. он получил разрешение по смерти быть захороненным самому и его второй жене Марии Ивановне.[4]

К приходу относились дер. Ново-Александровка (она же Еврееиновка) и хутора: Птушка и Земляной, прихожан на 1911 г. было 2297 человек.  При храме на 1911 г. действовали церковноприходская и три земские школы. Одна земская школа была в дер. Ново-Александровка, вторая в хут. Земляном, остальные в самой Мезеновке.[5] Законоучителем в них был священник Алексей Антониевич Подольский

В 1930-е годы стал складом для зерна. В 1960-х годах уничтожен.