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

Менее вероятная, но возможная версия — прозвище по профессии или ремеслу. В старопольском языке «klen» могло означать не только дерево, но и особый вид клея или смолы (ср. чешское «klíh» — клей). Тогда Кленевский — потомок смолокура, мастера по изготовлению клея. Однако эта гипотеза слабее, так как суффикс -ский типичен именно для шляхетских и географических фамилий, а не для ремесленных прозвищ.

В России фамилия закрепилась в основном среди потомков польской шляхты и униатского духовенства, которые после разделов Речи Посполитой поступали на русскую службу. В дворянских родословных книгах западных губерний (Виленской, Ковенской, Волынской) фамилия Кленевский встречается с XVIII века. Правописание через «е» после «н» — стандартное для русского письма, хотя в польском оригинале возможен вариант Kloniewski (с «о»). Такая замена «о» на «е» в безударной позиции характерна для адаптации польских фамилий в русской среде.

Если сравнивать с однокоренными фамилиями: Клёнов, Кленов — более простые, крестьянские по происхождению (от прозвища по дереву), а Кленевский — с явным указанием на местность, что обычно для мелкопоместной шляхты. Так что предки носителей фамилии Кленевский, скорее всего, владели или жили в небольшом имении Кленево где-нибудь на территории современной Беларуси или восточной Польши.