Існує припущення, що в давнину у селі Черешенька вже існувала невелика церква.

Нинішній храм святителя Миколая почали зводити у 1885 році завдяки пожертвам графа Васілка та селянської громади. За переказами, будівництво тривало десять років, а ще через десятиліття – у 1905 році – храм було освячено. За іншими джерелами, освячення відбулося у 1903 році.

У радянський час храм залишався діючим і не зачинявся. Востаннє значні зовнішні оновлення проводилися до 2015 року, коли громада святкувала 110-ліття храму.

Святиня збудована у традиційному стилі храмового зодчества кінця XIX століття. Біля храму розташована двоярусна дерев’яна дзвіниця, що знаходиться з південного сходу від будівлі. Оновлений зовнішній вигляд храму гармонійно поєднує історичні риси з сучасними елементами догляду та збереження.