Stavba kostela byla zahájena v roce 1525 a dokončena v roce 1529 na malé vyvýšenině západně od centra Klimkovic. Iniciátor její výstavby byl majitel klimkovického panství Hynek I. z Vrbna, který jej určil pro katolické věřící. V té době se v Klimkovicích nacházel dřevěný kostel svaté Kateřiny, který vlastnili evangelické komunity. Následující období bylo pro kostel značně turbulentní – střídavě přecházel do rukou katolíků a evangelíků. V roce 1681 ho majitelé panství Wlczekové stanovili jako farní kostel sv. Kateřiny a kostel Nejsvětější Trojice svěřili evangelickým věřícím. O osmdesát pět let později, v roce 1766, byl ke kostelu přemístěn hřbitov z centra Klimkovic a stavba tak získala nový účel jako kostel hřbitovní.

Během druhé poloviny 18. století a následujícího století byl kostel opakovaně stavebně upravován – konkrétně v roce 1805, v devadesátých letech 19. století a v roce 1934. V roce 1973 pohřbívání na hřbitově skončilo a prostor byl upraven jako veřejný park.

Architektonicky jde o renesanční jednolodní orientovanou stavbu na obdélníkovém půdorysu zakončenou trojbokým kněžištěm, k němuž ze severní strany přiléhá sakristie. Dvouhřebenová sedlová střecha s valbami nad kněžištěm je krytá břidlicí a na jejím hřebeni se vypíná sanktusník se stanovou střechou. Hladké průčelí je členěno opěrnými pilíři a podélnými okny s půlkruhovým záklenkem. Západní průčelí dominuje vstupní portál se segmentovým záklenkem, nad nímž se tyčí vysoký zděný trojúhelníkový štít. Vnitřek kostela poznamenává trámový strop s malovaným podhledem a v západní části se nachází kruchta.

Součástí kulturní památky je socha svatého Jana Nepomuckého z roku 1736, vytesaná z pískovce. Skulptura v tradičním esovitě prohnutém rouchu drží v náručí kříž a hlavu jí chrání kvadrátek a kovová svatozář s hvězdami. Sokl je zdoben protáhlými volutami a masívní římsou, na čele nese nápis s chronogramem.

Pozoruhodným objevem byl v únoru 2017 nález série jedenácti grafik Křížové cesty z přibližně 18. století, která byla skryta za krovy kostela. Autorem je pravděpodobně Johann Rugendas z augšburského tiskařského a malířského rodu. Grafiky v ozdobných rokajových rámech z pálené hlíny a glazury byly restaurovány Univerzitou v Pardubicích s finanční podporou Moravskoslezského kraje a v roce 2019 byly umístěny jako trvalý inventář na stěny lodi.

Kostel Nejsvětější Trojice byl do Ústředního seznamu kulturních památek České republiky zapsán v roce 1966. Dnes jej město Klimkovice udržuje a občas jej využívá pro koncerty a výstavy, čímž oživuje tuto renesanční stavbu novým účelem a zpřístupňuje veřejnosti její bohatou minulost.