Фамилия Терелецкая принадлежит к распространённому у восточных славян типу фамилий на -ский/-цкий. Такой суффикс чаще всего указывает на географическое происхождение: его давали тем, кто владел землёй или происходил из определённой местности. В основе фамилии лежит топоним Терелец или Терельцы. Такое название могло принадлежать небольшому селу, урочищу или хутору. Искать его стоит на территории современной Беларуси или западной Украины — именно там фамилии с окончанием -ецкий и -ельский особенно характерны. В польской ономастике, например, известна фамилия Terelecki, что подтверждает западнорусские или шляхетские корни.

Сама основа «Терел-» не имеет однозначного толкования. Самая вероятная версия связывает её с диалектным словом «терель» — так в некоторых говорах называли болотистую, топкую местность, заросшую осокой. В таком случае прозвище или название поселения означало «живущий у трясины» или «выходец из Терельцев». Менее распространённая гипотеза возводит основу к личному имени Тереля — уменьшительной форме от Терентий (через народное Терёха). Но для фамилии на -ский такая модель менее типична: обычно от имени образовывали фамилии на -ин или -ов, а не на -ский.

Если принять топонимическую версию, то первый носитель фамилии Терелецкий (мужской вариант, от которого образована Терелецкая) был либо помещиком, которому принадлежало имение Терельцы, либо крестьянином, переселившимся оттуда. В XIX веке фамилия фиксируется в Волынской и Гродненской губерниях, что совпадает с ареалом бытования польских и белорусских фамилий на -цкий. Женская форма Терелецкая, соответственно, закрепилась за дочерью или женой Терелецкого.

С точки зрения словообразования фамилия прозрачна: корень терел-, суффикс -ецк- (с чередованием ц/к) и окончание -ая. Ударение, скорее всего, падает на второй слог — Тереле́цкая, хотя в разговорной речи встречается и вариант с ударением на третий. Фамилия редкая, не входит в сотни самых распространённых, что делает её хорошим маркером для генеалогического поиска: все носители, вероятно, восходят к одному небольшому роду из западных губерний Российской империи.