Фамилия Оселедко напрямую связана со словом «оселедец» — так на Украине и в Белоруссии называли длинный чуб, который носили на бритой голове. Сегодня это слово почти забылось, а в старину прическа была настолько распространена, что дала начало целому гнезду прозвищ и фамилий. Самый известный образ такого чуба — на картине Репина «Запорожцы пишут письмо турецкому султану»: казаки с длинными чубами, перекинутыми за ухо, выглядят как иллюстрация к значению фамилии.

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

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

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

Фамилия бытует преимущественно в Украине и среди украинской диаспоры, в России встречается реже и чаще всего у потомков переселенцев. Точной статистики по числу носителей нет, но фамилия не относится к редким: она встречается в реестрах запорожских и полтавских родов, а также в документах XIX века по Харьковской и Черниговской губерниям. Сословной привязки у фамилии нет — ее носили и казаки, и крестьяне, и мещане, что лишний раз подтверждает: прозвище давали по внешности, а не по роду занятий.