魏姓是黄帝的姬姓嫡裔。周文王第15子毕公高受封于毕，其孙毕万在毕国被西戎攻灭后，投奔到晋国，成为大夫。魏，本为西周封国，公元前661年为晋国所灭，封大夫毕万于此地。魏城在今山西芮城县北。其后子孙以邑为氏，称为魏氏。
根据史学家的研究，大约6500年前，在以宛丘（今河南周口市淮阳县）为中心的黄淮区域，被尊为“人文始祖”、“三皇之首”的太昊伏羲统一了九大部落，奉“龙”为华夏图腾。中国人的姓起源于五六千年以前的母系社会。来自于部落的名称或部落首领的名字。因此中国最古老的姓大都是“女”字边，如姬、姜、姚、姒，妫，嬴等。它的作用主要是便于辨别部落中不同氏族的后代，便于不同氏族之间的通婚。氏早在传说中的黄帝时代就已经出现了。氏的大量出现是在周朝。周朝初期，周王大规模分封诸侯，此后这些诸侯国的后人就以国为氏了。另外，诸侯国又对国内的官员进行分封，这些官员的后裔就以封地为氏。据研究，中国人中所使用的99%的姓氏是从姓中派生出来的氏演变而成的。
姓和氏的意义本来并不一样，据东汉时的许慎在《说文解字》中解释，“姓，人所生也。…”氏则为姓的分支的含义。据石玉新等著的《华夏姓氏考》中介绍，上古三代（夏商周时）时代姓的产生是因生赐姓，作用是别婚姻，而氏则最初表示姓的分支，作用是区别贵贱。上古时姓和氏是有严格的区别的。到了战国时期姓氏制度发生混乱，周期的春秋战国完成姓氏合一，成为目前所表示的含义。
据多种史籍记载，对魏氏的“魏”字,通常有四种释义：
一是,《说文》释曰：“魏者，高也，大也”，与《古文》所言“巍巍乎”之巍意相同，且乃古“巍”字的缩写；二是，另据《逸周书谥法解》五十四之谥示，魏即“克威捷行”（意为有威面敏行）、“克威惠礼”（意为虽威而不逆礼），两者合之，即为“有威敏行，蕴威惠礼”曰“魏”；这里所说的“克威”是指有能尽力，“敏行”是指善行大道，“惠礼”则是“行唯仁适礼也”；三是，《左传》云：“魏者，大名也”；《广雅训诂》释“魏”为“好”，《方言》第十三释“魏”为“能”；四是，《玉篇?鬼部》解：“魏，象魏，阙也”，魏即指阙宫门之台观；《文选?班固<典引>》谓之：“是以来仪集羽族于观魏。”张钦注说：“来仪，凤也，……观魏，皆阙也。”故而，今有学者将魏姓的特点用“魏指宫门观全局，民族根本永屹立”来高度概括，颇为言之有理，恰当、妥贴。
魏姓来源有三：
1、出自姬姓，以邑为氏，或以国名为氏。
据《元和姓纂》所载，魏姓是黄帝的姬姓嫡裔。周文王第15子毕公高受封于毕，其孙毕万在毕国被西戎攻灭后，投奔到晋国，成为大夫。魏姓诞生距今已2666年。
魏，本为西周封国，公元前661年为晋国所灭，封大夫毕万于此地。《左传?闵公元年》载：“晋侯作二军，公将上军，大子申生将下军。赵夙御戎，毕万为右，以灭耿、灭霍、灭魏。还，为大子城曲沃，赐赵夙耿，赐毕万魏，以为大夫。”《魏世家》所载略同：“献公之十六年(前661)，赵夙为御，毕万为右，以伐霍、耿、魏，灭之。以耿封赵夙，以魏封毕万，为大夫。”魏城在今山西芮城县北。其后子孙以邑为氏，称为魏氏。
晋公子重耳流亡之时，毕万的孙子魏?随同一起流浪，后得秦穆公之力，重耳被迎立为晋国国君，是为晋文公。文公封魏?（WeiChou）世称魏武子为大夫，承袭魏氏封邑。据《魏世家》，魏武子之子悼子时，又徙治霍（今山西霍州西南）。
公元前451年，魏桓子与韩康子、赵襄子伐灭知伯，分其土地。公元前445年，毕万后代魏斯演出了历史上著名的“三家分晋”，自成诸侯，建立魏国，称魏文侯，建都安邑(今山西夏县西北)，正式确定了魏国的领土范围。
公元前225年被秦所灭后，亡国的魏国王族以国名为氏，形成魏姓最重要的一支。史称魏姓正宗。
2、外姓改姓魏。
战国秦昭襄王时有国相、穰侯、昭襄王母宣太后异父弟魏冉，本楚人，芈姓，后改姓魏；
南宋魏了翁，字华父，邓州蒲江（今四川蒲江县）人。生于南宋孝宗淳熙五年（1178年），卒于宋理宗嘉熙六年（1237年），自称出生于一个“贫贱”的家庭。他的曾祖父魏大昕，祖父魏苹，父亲魏士行都未作过官。魏了翁原不姓魏，其生父为高孝(王寿)，与魏士行是亲兄弟，因魏了翁的祖母高氏之兄无后，乃将孝(王寿)过继高家，孝(王寿)生有六子，了翁排行第五。后又因魏士行无子，再将了翁过继给魏士行为子，又改姓魏。
明代有昆山人唯校，其先世本李姓，居苏州葑门的庄渠，弘治进士，授南京刑部主事，后改姓魏。
3、少数民族姓魏。
随着历史的发展，一些少数民族除了本民族的姓氏，也采用汉族的姓氏，由于音近、省宇等原因，有以魏为姓的。
北魏时期氏族中有魏揭飞，自称大将军、冲天王；满族倭彻赫氏后改为魏姓；佤族斯内氏，汉姓魏；鄂伦春族魏拉依尔氏，汉姓魏。此外，土家、蒙古、彝、回、朝鲜等民族中均有魏姓。
回族中的魏姓，早期见于明代魏实。洪武年间（1368－1398年），武略将军魏实由顺天府（今北京）调湖南常德卫，路经湖北仙桃，见该地有清真寺及穆斯林居住，逐留其一子，后子孙繁衍，遍及湖北全省。（参见《湖北回族》）另，在广州怀圣寺《重建怀圣塔寺之记》碑中有“镇守广东等处地方副都统魏黑纳篆额”的记载（碑立于清康熙三十七年）。其名“黑纳”，按阿拉伯语发音有庆贺、祝贺、颂扬等意，较适用于取名；在古代进人中国的阿拉伯人名中，又有Hindu，也可简译为“黑纳”。魏黑纳恐是中国姓加上回回名的合成名。在清同治年以前，魏姓在西北地区亦为大族。据《同治年间陕西回民起义历史调查记》载，魏姓在同治年间是“咸阳的回族大姓”。仅道光年间，在咸阳县志中记载的东乡安谷里魏家村、西乡廊里魏家堡、魏家前村就有魏姓50户之多。魏姓回族，在中国革命近现代历史上也曾做出过一定的贡献。如在辛亥革命武昌起义中牺牲的有湖北两阳（今仙桃市）人魏碧章、魏清光；在北上抗日和解放战争中牺牲的有湖北郧西人魏茂顺、魏登恒等。魏姓回族主要分布在湖北、河南、甘肃等地。
与魏同宗者，据《元和姓纂》载，毕万封魏，支孙食采于冯为氏，季孙食采于潘为氏，毕公高之后有藩氏。续通志氏族略云：明时有藩俊者，系嘉靖举人，后任广东省清远知县。郡望荥阳郡故魏、毕、冯、潘、藩氏同宗。
毕公有后代子孙因故散居京兆、河间一带,以本为王族之故,自称为王。
春秋时晋国有吕氏，系从魏氏分化而来。魏武子(魏?)次子魏（金奇）封于吕、厨，所以又称吕（金奇）、厨武子。其后子孙以邑为姓。
据《通志?氏族咯》所载，战国初年，赵、魏、韩三国分晋后，公元前361年魏惠王江都城迁至大梁（在今河南开封市），魏惠王迁都大梁为梁惠王，子孙以梁为氏，是为河南开封梁氏。
与魏姓有渊源的还有令狐氏，《百家姓》中记述为：周朝时有个叫魏颗的人屡立战功，受封于令狐邑，后人遂以令狐为姓。
据史料记载，万姓亦源於周朝姬姓王室，他们的后裔中先后有两房人改姓为万。周初重臣毕公高之后毕万，后去晋国效力，封为大夫，是晋国战功显赫的将军。毕万帮助晋国征服魏国之后，晋献公将魏国封给毕万，所以毕公又称魏万。毕万系魏姓得姓始祖、也是万姓始祖。
魏氏早期主要是在今山西、河南、山东省境内发展繁衍，也有部分分居于今湖北、湖南省境内。战国时信陵君魏公子无忌子录番盛，知名度高，所以诸多古籍和魏氏族谱大多以魏无忌为魏氏承上启下的关键人物。秦汉之际，魏姓进一步扩展到陕西、甘肃、宁夏等为主的北方广大地区，一支迁入四川。
《新唐书.宰相世系表》在简述魏系从毕万至昭王生公子无忌后，接言：“孙无知，汉高梁侯。生均。均生恢，恢二子：伯纶、彦。彦字叔纶，张掖太守。生歆，字子胡，巨鹿太守，初居下曲阳。二子：愉、悦。愉字修长，侍中。……”