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

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

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

Географически фамилия Мажейко тяготеет к западным регионам бывшей Речи Посполитой — современным Беларуси, Украине и восточной Польше. Встречается и у русских, но как результат миграций. Среди однокоренных фамилий — Мажей, Мажейкин, Мажейский; все они восходят к той же основе, но различаются суффиксальным оформлением, типичным для разных регионов.