Точна дата виникнення села Телелинці невідома. У письмових джерелах збереглися відомості про існування села в першій половині XVIII сторіччя. Як зазначалось у праці Єфима Сецинського, «село розташоване у низині, поблизу невеликого ставка; від найближчої залізничної станції Жмеринка на відстані 18 верств. Ґрунт піщаний, а місцями чорноземний. За повір'ям, на місці села колись був густий ліс з чудовими галявинами; в цій місцевості оселився Тулин зі своєю родиною без відома власника, й утворилось поселення, яке спочатку отримало назву Тулилинці. Поселення відносилось до приходу села Мовчани, а згодом мешканці побудували свою власну церкву. Перші два священики були уніатами; кінець унії поклав священик Іоанн Бицькій, який разом з парафіянами приєднався до православ'я. Нині парафіян обох статей 1350 душ; усі вони — селяни-малороси, землероби; дехто з них займається теслярством або ткацтвом. Перший храм, дерев'яний, на честь святого Архистратига Михаїла зведено 1739 року завдяки старанням парафіян, місцевого власника і священика Гавриїла Бєлінського; у цьому ж храмі був священиком і син Бєлінського. Храм цей був пошкоджений внаслідок пожежі, але згодом відновлений, нині будівля його стара. Церковної землі: помістя 3 десятини 1061 саженів, ріллі 30 десятин, сінокосів 3 десятини 1024 сажені. Будинки церковні споруджені 1895 року на кошти поземельного податку. Церковна школа відкрита священиком Андрієм Короповим 1865 року; розміщена нині у його власному будинку».