及至徐州，幸謁劉備，喜曰：“真吾主也。”劉備授幸別部司馬，張飛守下邳。數日之間，呂布亦至。劉備征袁術，布乘虛襲下邳，虜劉備妻子與幸。布素惡幸，遂放歸劉備。劉備還駐小沛，使幸糾合軍卒，複合萬餘人。布疑而攻之，卒嘩亂四潰，劉備敗投太祖。
步幸字吉利，冀州鄴城人也，良家子。中平初，黃巾大起，幸隨大方首領馬元義，為籌劃事。元義聚眾數萬於鄴，期三月五日舉兵。未發，元義弟子唐周密報於朝廷，事敗，元義伏誅。幸亡歸張角。
三十六方黃巾俱起，天下響震。張角以四方有事，遣幸往援南陽張曼成。幸甫至，適南陽太守秦頡進剿，曼成尋敗死。眾推曼成副將趙弘為督，據宛以自保。幸說弘曰：“固守不佳，久必成困，未若乘夜以勇士衝之，敵必驚潰。”弘從其計，輕軍襲營，為流矢所傷，半旬而亡。弘副將韓忠繼執帥印，以幸為謀主。十月，忠沒於軍中，宛城乃陷。
幸往歸張角，及至河北，角病死，乃複投張梁。時梁與皇甫嵩戰於廣宗，幸懲宛城之事，料敵必不敢輕進，梁遂不以為備。嵩潛夜勒兵，乘暮急攻之，陣斬梁並黃巾軍三萬餘級。幸僅以身免，入下曲陽張寶營下。十一月，嵩破下曲陽，寶即就戮。黃巾十數萬人一時俱死，哀聲遍野。幸立於敗軍之地，麵色如舊，談笑如常。嵩見之頗奇，收為幕僚。
明年春，詔嵩回鎮長安，以衛園陵。幸隨入洛陽，嵩被收左車騎將軍印綬，削戶六千。
靈帝崩，少帝即位。何進謀誅閹官，廣選人才，嵩進幸，進授以軍司馬職。未幾，黃門常侍段珪殺進，俘幸等僚屬百餘人為質，縛於掖庭。幸急曰：“吾，黃巾舊部也，非大將軍嫡屬。”珪等久居內闈，不通治戎，遂著幸執掌宮門宿衛。
是夜，袁術虎賁鼓噪於外，袁紹勒兵大進，宮內大亂。珪等挾帝並陳留王走小平津，幸隨駕左右。後珪等窘頓無路，投水而死，幸扶幼帝、陳留王欲回宮，闇暝，逐螢火而行。行至北芒，董卓軍至。