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

Скорее всего, имя Майба относилось к так называемым охранительным именованиям. По народной логике, назвав ребёнка словом со значением страдания, родители «обманывали» злые силы: желая младенцу счастливой и безбедной жизни, они давали ему имя с противоположным смыслом. Таким образом, имя Майба должно было защитить ребёнка от горя и нужды.

Географически фамилия Майбин и её производные встречаются редко и имеют локальный характер, что типично для фамилий, образованных от нецерковных имён с редкими суффиксами. Модель на -ба (как в фамилиях Журба, Скорба) больше свойственна украинской и белорусской ономастике, хотя сам глагол «маяться» общеславянский.

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

В отличие от более распространённых фамилий на -ов, форма на -ин часто указывает на основу, оканчивающуюся на гласный или мягкий согласный, что и произошло с именем Майба.