新朝末年，由于王莽在统治期间屡次改变币制，造成经济上的混乱状态，法令苛细，徭役繁重，社会矛盾激化。公元17年，终于爆发了全国性的农民起义。西汉的皇族刘秀，乘机和兄长刘演起兵响应，加入绿林起义军。行军途中，有个名叫王霸的带领一批人来投奔刘秀，受到了刘秀的欢迎。后来，他跟随刘秀出战新军，建立了不少功勋。
不久，王霸因父亲年老体弱，辞别了刘秀回家待奉老父。后来刘秀率军又路过王霸老家的时候，特地去看望他。王霸深受感动，请求父亲让他离家再追随刘秀。他父亲深明大义，说：“既然刘将军如此看重你，你就跟他干下去吧，不要半途而废。”
就在这一年，也是西汉皇族而被起义军推为更始将军的刘玄称帝，年号更始。更始帝对刘秀兄弟十分猜忌，杀害了刘演。刘秀怕遭到杀害，请求他派自己到河北去招抚各州郡归顺，刘玄同意了。刘秀命王霸随他前往河北。当时，更始帝的势力末能达到河北，到那里去招抚是很危险的。
刘秀一行进入黄河以北后很不顺利，处境非常危险，也非常困乏。随从中许多人对前途失去了信心，又害怕艰苦，纷纷离开了刘秀。先前和王霸一起投奔刘秀的几十个人，都陆续不辞而别；只有王霸还和以前一样，忠诚地跟着刘秀。刘秀见王霸至今还忠于自己，感慨地对他说：“从前在颍川跟随我的人都跑了，唯有你独留在我身边。只有在迅猛的风中看出坚韧的草，这话现在得到了验证。”
刘秀在河北积极活动，以恢复汉家制度为号召，取得了部分官僚、地主的支持，镇压和收编了起义军，力量逐步壮大起来。公元25年，他利用农民起义的力量，终于推翻王莽政权，即皇帝位，史称东汉光武帝。王霸也被封为富波侯、偏将军、讨虏将军。