步姓的起源有多種說法，主要包括以下幾個方面：
出自姬姓：春秋時期，晉國大夫叔虎有三個兒子：稱、芮、義。義的兒子孫子名揚，被封於步邑，因此被稱為步揚，他的後代以邑為姓，稱為步氏。步揚被視為步姓的得姓始祖。
出自北方鮮卑族三字姓所改：南北朝時，北魏鮮卑族有步鹿根氏，入中原後逐漸與漢文化融合，改為單姓步氏。
源於官位：
春秋時期官吏步丈人，屬於以官職稱謂為氏。步丈人全稱為步尺人，亦稱丈步人，是西周初期輔政大夫召公奭所設定的官位。
漢朝時期官吏步兵校尉，亦稱步兵將軍，是漢武帝劉徹在公元前140年設定的軍制官位，屬於以官職稱謂為氏。
源於姜姓：春秋時期齊國貴族叔步乘，是孔子的七十二賢門徙之一，屬於以先祖名字為氏。
源於鮮卑族：古鮮卑族步祿孤部落，屬於以部落名稱漢化為氏。
源於滿族：金國時期東真國國主蒲鮮·萬奴的後裔子孫，屬於以部落名稱漢化為氏。
步姓是一個多民族、多源流的古老姓氏，在中國大陸和台灣省均未列入百家姓前三百位，在宋版《百家姓》中排序為第三百四十八位門閥。