1898年农历三月十六日，山东曹州府（今山东荷泽县）赵楼村一户寻常农民家，伴随着一阵清亮的啼哭声，一个新生命诞生了，他就是赵登禹。赵登禹，字舜诚（又作舜臣），因排行老三，有小名“小三儿”。祖上世代务农，父母均为勤勉诚实的农民，靠耕种几亩薄地为生。有两个哥哥，大哥赵登峦，忠厚老实，为人持重；二哥哥赵登尧，喜好武术，好打抱不平，行侠尚义，遇有不公，挺身相助，在当地小有名气。此外，赵登禹还有两个妹妹。由于家境清贫，两个哥哥均没能上学。等到赵登禹长到7岁时，因其聪明伶俐，父母也觉得家里总得有个弄文舞墨的人，加上邻人的劝告，便省吃俭用，将其送入学堂读书。然而，好景不长，终究因家境困难，父亲身体又不好，靠母亲一人里外操持，更是艰难，因此两年后赵登禹不得不辍学回家，离开了他喜爱的学堂。回到家里的赵登禹即开始帮助父母做力所能及的农活。他不怕苦不畏累，就是一些大人们干的重活，他也尝试着去做。艰苦的生活，沉重的劳作，不仅没有将小小年纪的赵登禹压垮，相反倒使其练就了一个好身体，磨练了他吃苦耐劳的意志，使其在后来的戎马生涯中不畏艰危，不怕辛劳。荷泽一带素有习武风气，人们一则以练武强身，二则练习一些武艺以自卫，加上受哥哥练武的影响，因此，在劳作之余，赵登禹也开始练习武术。起初，他跟着哥哥赵登尧及村里其他习武的年轻人练，1910年13岁那年，正式拜当时荷泽一带较有名望的武师朱凤军为师，开始系统地练习武艺。他练功很刻苦，尽管一天的劳作已很辛苦，但他从不停止练习，就是再累，他也要练上一会。很快3年过去了，赵登禹不仅练就了一身基本的武术根底，同时在练武过程中，逐步对见义勇为、行侠施义的武德有所认识，养成了刚毅耿直、嫉恶如仇的豪爽性格。他有强烈的正义感，遇有不平，敢于挺身而出。为此他赢得了贫苦乡亲的称赞，但同时也得罪了一些有钱有势者。也许是不满于家乡富人的横行不法，鱼肉乡里，或许是不满足于自身的状况，欲求更大的发展，以实现行侠施义的愿望，总之，伴随年龄的增长，赵登禹萌发了当兵的念头。在十多岁的赵登禹心目中，也许认为唯有当兵才能实现其抱负。但投奔谁的门下，当什么样的兵，年幼的赵登禹却不是盲然的。当听说北洋冯玉祥部队军纪严明，作战勇猛，爱护百姓，遂下定了投奔冯部当兵的决心。1914年初秋，赵登禹与同乡赵学礼、赵全胜等人，瞒着家人偷偷离家出走，准备投奔驻潼关的冯玉祥部队当兵。由荷泽去潼关，有1800多里地，几个年轻人一路跋涉，风餐露宿，出门时带的几个钱，很快就花完了，他们就靠帮人打工扛活挣几个吃饭钱。经过20多天跋涉，终于到了潼关。然而他们到了才得知，部队招收新兵工作已经结束，且招收名额已满。伙伴们都很泄气，有的主张返回荷泽。但赵登禹坚决不同意返回荷泽，主张坚持努力，一定要当兵。他们几个人找到主持招兵工作的官长，软磨硬泡，好说歹说，终于说服负责官长同意，但因名额已满不能作为正兵，只能作“副兵”，只吃粮不发饷。由此赵登禹开始了其军旅生涯。冯玉祥部队当时属袁世凯北洋陆军第7师第16混成旅，冯玉祥为旅长。赵登禹入伍后，被编入第1团第3营第2连，连长即为后来成为第29军副军长的佟麟阁。因为赵登禹生得膀大腰圆，体魄强健，同时他为人正直，办事机敏，因此很受佟的赏识。训练中，赵登禹非常刻苦，对自己要求很严格。因为他有武术的根底，加之训练用功，因此在许多训练课目中都名列前茅。
1915年春，冯玉祥部队奉命入川。袁世凯原打算派冯玉祥入川监视西南地方势力，以免他们起而反对他的复辟帝制活动。然而冯玉祥入川后采取观望态势，按兵不动。同年底，讨袁护国战争爆发，冯审时度势，起而参加护国战争，所部改编为护国军第5师。这期间，赵登禹随部参加了护国战争，且作战非常勇敢。
1916年袁世凯死后，冯部转调平津之间的重镇廊坊驻守。一次偶然的机会，冯玉祥在众多的士兵中发现了赵登禹。这一天冯玉祥检阅部队时，发现行进的队伍中，有一名大高个士兵的步伐与整个队伍的行进步伐很不协调，仔细一看他是趿拉着鞋走路。冯玉祥很是生气，当即命令部队停下，走到大个子士兵面前严厉斥问他是怎么回事。这个大个子士兵就是赵登禹。原来因他长了一双大脚，部队军需部门一时又没有这么大的鞋，故只能穿着小鞋拖着走。冯玉祥知道事实真相后，不仅没有批评他，相反他见赵登禹长得膀大腰圆，体壮如牛，非常高兴。当时他叫来军需官，让其迅速想办法给赵登禹定做大号鞋，解决他的穿鞋问题。这一偶然事件，对赵登禹以后的军旅生涯产生了重要影响。此后，冯玉祥开始注意赵登禹，了解到他不仅生得体格强健，且练过武术，有相当的武功根底后，冯更加高兴，因为他本人就是武术高手，刀术更是高明。同时，冯玉祥又得知赵登禹训练非常刻苦、用功，作战很勇猛，且能弄文舞墨。由此，冯玉祥就把赵登禹调到自己的身边，当了自己的一名护兵。
能够给冯玉祥当护兵，对于普通士兵来说，这是一件很荣耀且有着更多发展机会的事，因为他不仅能随时见到冯玉祥，且能见到许多其他高级军官。赵登禹很珍惜这个机会，尽心尽力完成护卫任务，很受冯玉祥的信任与称赞。据说有一次，赵登禹跟随冯玉祥检阅部队，检阅过程中，他突然发现有一刺客欲刺杀冯玉祥，情急之中，他当即向刺客扑了过去，在其没来得及行刺时，就将其打翻在地，保卫了冯玉祥的生命安全。
在完成护卫任务的同时，赵登禹利用能够经常接触冯玉祥的机会，了解、观察冯玉祥的为人处世及治军治学方法等，并从中学习有用的东西。冯玉祥治军甚严，并高度重视部队的政治教育工作。部队训练中就有“政治”一项，他自己并曾亲自为战士上政治课，以“不扰民，真爱民，誓死救国，反对官僚政府，反对外国侵略”等朴素的爱国爱民思想来教育战士。他还礼聘了一批知识分子，编写了《识字课本》、《精神书》、《军人宝鉴》等通俗易懂的小册子，供战士们学习用。由于冯的倡导，部队中形成了识字读书明理知事的风气。冯玉祥本人更是带头读书，在其读书时，他要求赵登禹对来访的人，无论是谁，一律挡驾，概不会客。正是在冯玉祥的言传身教下，赵登禹逐步养成了读书学习、明辩事理的良好习惯，以后又经冯玉祥的帮助，进入西北军教导团学习，为其今后的进一步发展打下了良好的基础。
1917年秋，赵登禹随冯玉祥进驻湖南常德。当时常德驻有日本的领事馆，还有一些日本侨民浪人散居其间。这些日本人依仗其领事馆的势力，经常寻衅滋事，并勾结当地的歹徒，横行不法，欺压百姓。当地的官府害怕日本人势力，明知他们横行不法也不愿、不敢去管，老百姓更是敢怒不敢言。赵登禹住了一段时间后，发现了这一情况，很是气愤，强烈的正义感促使他决心寻机管一管他们。
机会来了。一次，几个日本浪人酒后寻衅闹事，在街上与几名中国小商贩发生争执，争执中这些日本浪人大打中国商贩。赵登禹得知情况后，当即带人赶到，将几个日本浪人狠狠地揍了一顿，然后将他们带回冯玉祥的司令部，交冯处理。冯玉祥听了事情汇报后，义正辞严地怒斥了日本浪人的不法行为，并向当地日本领事馆提出交涉。经多次协商，最后迫使日本领事馆出面向我方赔礼道歉，并保证以后对日本浪人严加管教，保证不再重犯。这样冯玉祥才下令将闹事的日本浪人放回。此举深得当地老百姓的称赞，赵登禹也因此事更得冯玉祥的赏识。
驻常德期间发生的另一件事，更显示出赵登禹的勇猛。当时，常德附近山上常有老虎出没，伤害人畜，周围百姓受惊害怕，深受其害。有一次赵登禹上山执行任务时，突遇一只猛虎。危急关头，他不急不躁，机敏地躲过猛虎的扑咬，与其周旋，最终将这只危害百姓的恶虎击毙，并与同行的士兵们一起将老虎抬下山来。四乡八村的百姓们听说此事，非常高兴，钦佩赵登禹勇猛机智，为民除害。冯玉祥得知此事后更是格外高兴。他亲自让人请来摄影师，为赵登禹照了一张像，并亲笔在照片上题写了“打虎将军”几个字。
这一期间，赵登禹还随冯玉祥两度入陕西，其中1921年第二次入陕，冯玉祥击败其他军阀的部队，出任陕西督军。留陕期间，冯玉祥为清除陕西地方武装郭坚所部，假意拢络，设下鸿门宴请郭坚，预伏精壮兵士于屏风后，准备一举将其擒获。酒宴进行中，未到动手之时，设伏于屏风后的兵士因争看冯、郭对饮而将屏风推倒，郭坚见势不好，依仗其有一定的武功，意欲强行冲击。赵登禹见此情景，挺身而出，断其逃路。经过一番激烈的对持，终将颇有武名的郭坚生擒。
到1922年离护卫任他职，赵登禹一直在冯玉祥身边工作了6年。这是他一生中非常重要的6年，无论是军事技艺还是读书学习，他都有了长足的进步，思想意识亦有很大的提高。尤其是对冯玉祥治军练兵、作战风范的逐步认识与深刻领悟，对其以后领兵打仗、治军练兵有非常大的帮助。