Фамилия Старшина — один из тех случаев, когда прозвище, ставшее фамилией, прямо называло должность или общественное положение предка. В отличие от большинства русских фамилий на -ов и -ин, эта сохранила исходную форму слова в именительном падеже, что указывает на её относительно позднее закрепление — скорее всего, в среде казачества или вольных крестьян, где прозвища не спешили русифицировать суффиксами принадлежности.

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

Интересна география фамилии. По данным переписей XIX–XX веков, фамилия Старшина заметно чаще встречается на юге России — в бывших казачьих областях Дона, Кубани и Терека. Это косвенно подтверждает версию о казачьих корнях: именно там должность старшины была не просто административной, а воинской и наследственно престижной. В центральных губерниях фамилия встречается реже и часто имеет другую природу — могла возникнуть как «уличное» прозвище в среде отходников или ремесленников.

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