Фамилия Галайдин образована от личного прозвища Галайда. Основа прозвища восходит к украинскому слову «галайда» — «бродяга». Слово это, скорее всего, тюркского происхождения, что указывает на давние контакты славянского и степного мира. Так на Руси могли назвать человека, который не сидел на месте, часто переходил из селения в селение или вёл неоседлый образ жизни.

Фамилия построена по типичной русской модели: к основе на -а добавляется суффикс -ин, указывающий на принадлежность («чей?» — сын Галайды). Форма Галайдин, а не Галайдин, объясняется тем, что в диалектах и письменных источниках фамилии часто записывали на слух, и написание с буквой «и» в суффиксе закрепилось.

Прозвище Галайда не обязательно несло негативный оттенок. Бродяжничество на Руси было привычным явлением, а отношение к бродягам — двойственным. Церковь считала подаяние богоугодным делом, и государство долго не могло решить, как с ними быть. Иван Грозный приказывал строить для них богадельни. При Алексее Михайловиче нищие и бродяги жили в таких приютах, не оставляя своего ремесла. Царь Фёдор Алексеевич впервые попытался привлечь церковь к разделению бродяг на «страждущих» и «тунеядцев», предлагая первым помощь, а вторым — принудительный труд. Пётр I в 1712 году запретил просить милостыню под угрозой штрафа, но вскоре отменил указ, столкнувшись с религиозной традицией подавать «Христа ради». При дворе Прасковьи Фёдоровны, матери Анны Иоанновны, находилось множество бродяг, о чём писал историк Татищев. Екатерина II передала борьбу с бродяжничеством полиции, а при Александре I создали фонд помощи нищим, который пополнялся за счёт частных пожертвований и кружечных сборов.

Потомок человека с прозвищем Галайда, скорее всего, получил фамилию в XVI–XVII веках, когда процесс формирования русских фамилий шёл особенно активно. Точное место возникновения фамилии Галайдин установить сложно — украинское происхождение основы не обязательно означает, что предки жили на Украине. Прозвище могло появиться в южнорусских или пограничных землях.