呂姓來源有三：
一、是出自姜姓
以國為氏，始祖為伯夷。出自姜姓，是由古部族名和古國名、古邑名等而得姓。炎帝的後裔，共工氏從(堂)孫伯夷，是帝顓頊之師，帝堯時輔政，掌管禮儀，帝舜時正式任命他為秩宗。禹代行天子之政時，伯夷盡心輔弼，成為禹的心腹之臣。為嘉獎伯夷，帝舜晚年賜伯夷姓姜，賜氏為呂，並封他為呂侯，形成呂氏部族。伯夷的後代，早年活動於甘青山嶽地區，由於崇拜山嶽之神，形成了四岳部落。在堯、舜、夏禹時代，四岳成為部落聯盟的山嶽祭司。呂與申，皆為四岳部落之後，屬羌人的一支，是姜姓的重要分支。
原始社會末期，呂部族由羌人分出，與親族申部族由甘肅東部又向東遷。遷至上申川之北的呂川(今志丹縣東北的杏子河)。杏子河發源於靖邊縣的白于山，東流注入延河，後流入黃河。呂人順著延河河谷，東渡黃河，與申同時遷至今山西中部的呂梁山的。今山西鄉寧縣東南4公里地有呂鄉廢城是呂姓進入山西的落腳點。呂人在夏、商時世有其國，後又東遷至汾水中游肥沃的平原，今存古呂城遺址。
在商朝末年已有了呂姓，呂尚為呂侯的支系子孫，曾輔佐周文王;武王。這時期是呂姓的發端。呂尚，在當時又稱姜尚，人們仍以其祖姓姜稱呼他。
商朝末年，呂國成為周人的同盟，呂國的首領呂他幫助周武王打敗商王紂的同盟軍越戲方。周武王為獎賞呂人的功勞，建立周朝後封呂他為呂侯。周穆王時，呂侯為相，受命為周王朝制訂了有關刑罰的文告《呂刑》，它是世界上最古老的刑法條文之一，用以對付被征服的苗民。其刑法為五刑(墨、劓、(非阝)、宮、大辟)，共三千條。
周宣王立志復興周朝，大力經營南蠻、百濮、荊楚和淮夷，改封呂侯為甫侯，將呂國和申國從山·西南遷到河南的南陽一帶，鎮守南方。唐代司馬貞《史記索隱》引《地理志》云：“申在南陽宛縣，申伯國也，呂亦在宛縣之西也。”《括地誌》確切指出在呂在“南陽縣西三十里”。唐時，南陽縣治設在今南陽市臥龍區潦河鎮，其西“三十里”即今鎮平縣境。這一地帶即春秋以前的古呂國、戰國時期的呂邑、秦漢時的涅陽、呂城遺址。
呂國南遷之後，到周幽王時，申、呂的國勢漸衰，春秋初年，楚國強盛，向北吞併漢水流域諸國。公元前688年，呂與申、繒等被楚文王所滅。楚靈王時，呂部分遺民被遷至湖北蘄春。
南陽呂國被楚滅亡後，楚王將其遺族的一支東遷至今河南新蔡縣西南，建立了一個小國，為楚國附庸，史稱東呂，以區別於南陽之呂。後東呂被宋國所並，繼而又淪為陳的屬地，陳被楚滅，其地則歸了楚。楚平王時，令蔡平侯復國(蔡國曾為楚靈王所滅)。蔡平侯將蔡國從上蔡遷至東呂故地，該地遂改名新蔡。
西呂、東呂滅亡後，呂國子孫均以國為氏，形成呂姓的主脈。呂侯支系孫呂尚所建的齊國滅亡後，其裔孫分別以呂、齊為姓。
二、是出自魏氏
據《姓源》及《通志·氏族略》所載，春秋時晉國有呂氏，系從魏氏分化而來。山西的呂人故地，被晉國所並，晉侯將此地作為封邑，賞給姬姓公族大夫魏氏。魏氏後裔雖系晉之公族，姬姓，但因封於呂人的故地，因而仍襲用呂的故號。晉惠公時有大臣呂甥。《讀史方輿紀要》卷四十一霍州呂城條：“州西三里，故呂鄉，晉呂甥邑也，今有呂陂，在州西南十里，亦以呂甥名，隋因置呂州。”呂邑後被晉併吞，呂甥後代以邑為氏，形成呂姓。是為山西呂氏。
三、是出自少數民族改姓
鄭樵《通志·氏族略》載，鮮卑族原有叱呂氏、俟呂陵氏等複姓。北魏孝文帝遷都洛陽後，將鮮卑族複姓改為單字漢姓，叱呂氏改為呂姓。後周時，又將俟呂陵氏，改為呂姓。《通志·氏族略》中所列比邱氏、副呂氏後均改為呂姓。