秦二世（胡亥）元年（公元前209年）秋，陈胜与吴广等人在蕲县大泽乡（今安徽宿县东南刘村集）起义，迅速发展到几万人，并在陈县（今河南淮阳）建立张楚政权，陈胜被推为王。各地郡县纷纷响应，杀死当地官吏，起义造反。这时，刘邦与萧何、曹参、樊哙等人共谋，鼓动父老子弟杀死沛县（今江苏沛县）县令，大家拥戴刘邦做了沛公。这年九月，项梁和侄儿项羽杀死会稽太守殷通，取得精兵八千人，率兵渡江西进，驻军下邳（今江苏宿迁县境）。刘邦起义后，广招天下豪杰，扩军备战，以萧何、曹参为谋士，任樊哙、夏侯婴、周勃等人为将军。刘邦为人豁达大度，爱将如宝，从严治军，不准扰民，军民尽皆喜悦，投奔者众。一日，刘邦独坐营中，研读兵书，忽闻人报，有一壮士单骑来投，令人唤来。但见此人魁梧雄壮，气宇轩昂，心中甚为喜悦。问道：“壮士从何而来，家居何处？”纪信从容说道：“我名纪信，蜀地阆中县扶龙村（今西充紫岩乡纪公庙村）人。闻沛公起义攻秦，特慕名来投。”刘邦笑着说道：“壮士远道来投，助我攻秦，令人敬佩。观尔英姿勃勃，必是智勇之人，暂任部曲长之职，权居夏侯婴将军属下，待立功后，再行升赏。”立即唤来随从，领纪信去拜见夏侯婴将军。
夏侯婴将军见了纪信，异常喜悦，令其带领部从督察军纪民情。一日，纪信带领数人巡查至沛县街头，但见市井繁华，百姓安居乐业，一派升平景象。来到一个茶馆，见一绝色女子引颈高唱道：“云淡风轻近午天，傍花随柳过前川。时人不知予心乐，散步闲游赏名园。贪欢失迷芳草路，遥望见杏花村内酒旗翻。急急走，忙向前，沽饮三杯一齐干。只见那粉壁上画着一洞仙，手中拿着渔鼓板，原来是张果老儿一溜烟。白头翁相对红娘子，巧姻缘内会神仙。逍遥过，庆寿筵，身在蓬莱万万年。倒骑驴儿哈哈笑，他就是将谓偷闲学少年。”此女子生得美貌，歌也唱得好，众人听后，皆齐声喝彩，鼓掌大笑。纪信不便久留，信步前行，忽闻茶馆中传来一阵喧哗，急忙回转，查看实情。见一军汉，醉醺醺地调戏卖唱女子，女子严词正色，大声斥责，围观群众议论纷纷。纪信素恨强暴邪恶之人，立即上前将这军汉拉开，军汉怒骂不止。纪信将他扭见夏侯婴将军，女子哭哭啼啼跟随在后，很多百姓亦尾随而来。大家来到军营，百姓们停留在外，纪信押着军汉，带着卖唱女子，入见夏侯婴将军，说道：“此军汉醉戏民女，有损沛公禁令与威名，请将军严惩，以儆效尤。”夏侯婴将军问歌女道：“你是何地人，这军汉如何调戏你？从实说来。”歌女说：“我名李玉兰，豫郡柳园人，父母因病谢世，孤身漂泊来此。幸遇张老收为义女，教我唱歌糊口，不意被这军汉调戏，请将军为民做主，严治此人，以雪耻辱。”夏侯婴将军听后大怒，令将此军汉重责四十。笑向李玉兰说道：“你一个弱小女子，别无亲人可依，在这兵荒马乱之时，难免不受人凌辱。我欲将你许配纪信，玉成你俩的婚事，你愿意吗？”李玉兰说道：“将军爱护民女，情同父母，父母之命，焉敢不从。”夏侯婴又问纪信，纪信也很乐意。夏侯婴将军令人租赁民房，给纪信完婚，众官兵无不喜悦和敬佩。