Nazwisko zostało utworzone od nazwy osobowej Madej (zdrobniałej formy imienia Amadej ‘Amadeusz’ lub Matej ’Mateusz') i wskazuje na związek z ojcem lub innym przodkiem, który tak się nazywał.