Фамилия Лышенко образована от прозвища Лыша, и у этого прозвища есть несколько возможных объяснений. Первая версия ведет его к слову «лыщица» — так называли травянистое растение, корневища которого использовали для мытья шерсти. По народным представлениям, давая ребенку такое прозвище, родители словно «вверяли» его природе, чтобы к малышу перешли полезные свойства растения. В таком случае Лышей могли прозвать либо человека, который занимался мытьем шерсти, либо просто того, кто был связан с этим ремеслом.

Вторая гипотеза — топонимическая. На старых картах Российской империи встречаются названия Лышнова, Лышный и Лышни, особенно много их было на Вятке: деревня Лышнова в Яранском уезде, Лышный починок в Орловском уезде и еще один Лышный — в Вятском уезде. Не исключено, что предок носителя фамилии был выходцем из одного таких мест. Прозвище Лыша постепенно закрепилось за ним в качестве наследственного имени и со временем вытеснило первоначальное крестильное.

Сама фамилия построена по распространенной украинской модели с суффиксом -енко, который в XVI–XVII веках обозначал «сын» или «потомок» (Лышенко — буквально «сын Лыши»). В дальнейшем эта модель утратила буквальное значение и стала восприниматься как обычная фамилия. С точки зрения словообразования, Лышенко — типичная фамилия для территорий, испытавших влияние украинской ономастики, хотя прозвищная основа могла возникнуть и в севернорусских говорах, где были распространены вятские топонимы.