Rindzi 独立飞行大队进驻海拉尔之后没几天，5 月 20 日（日方记录）或 21 日（苏方记录），哈勒哈欣河上空爆发了第一次空战，一家执行战场侦察巡逻任务的苏军波利卡波夫 R-5 被日军 Ki-27 击落。在被袭击之后苏军针锋相对的派出战斗机在诺门罕上空磨拳擦掌，5 月 22 日第一次双方战斗机爆发首次正面交锋，日方的记录中，Ki-27 在巡逻中遭遇了 6 架 I-16 组成的机群，并将其中三架报销，苏方的记录承认了失败，但是细节上与日军有些出入：3 架 I-16 和两架 I-15Bis 被五架日军 Ki-27 偷袭，一架 I-16 不幸被击落，另一架虽然身负重伤，却安全降落。
诺门罕空战的第一位牺牲者是一架波利卡波夫 R-5
I-15Bis，海鸥，一款很经典的双翼机
与此同时，苏军和日军的司令部都在四处搜罗援兵充实本方的空军实力，苏军方面在 5 月 20 日之前的准备显得漫不经心，动起手来却发现对面的日本人明显是蓄谋已久有备而来。痛定思痛，苏联人以惊人的效率将战机塞满图门江等能够覆盖哈勒哈欣河的机场。
5 月 23 日，第 22 驱逐机团（the 22nd Fighter Air Regiment IAP）抵达蒙古东面的图门机场，其装备中最引人注目的是 28 架新式的 I-16 Type 10 型，这款 I-16 根据西班牙内战的经验，将火力提升了一倍，发动机罩和机翼上共安装了 4 挺机枪。发动机也改成 M-25B 型，也就是莱特旋风 R-1820-F-54 的苏联版，功率提升到 750 马力。此外驾驶舱也总算戴上了滑动舱盖，与国际先进接上了轨道。
另外第 22 驱逐机团还有 36 架老式的 I-15Bis，这批老式双翼机在之后的作战中大部分时间担任对地任务，其坚固的机体和灵活的身法还有翼下的火箭使得“海鸥”成为地面日军的噩梦。几天之后，59 架隶属第 38 高速轰炸机团（the 38th High-Speed Bomber Air Regiment SBAP）的 SB-2 也赶到了图门机场，这款被西班牙共和战士爱称为“Katyushka”的轰炸机在中国、西班牙和蒙古都表现不俗。
SB-2 是一款极为优秀的高速双发轰炸机
日本方面也始终没有停下增兵的脚步。5 月 24 日，第 11 飞行战队（the 11th Sentai）的两个中队（chutai）带着 20 架 Ki-27 飞抵海拉尔。三天之后日本人已经可以在哈勒哈欣河上空拍出 64 架飞机的庞大集群。而苏联人虽然在蒙古拥有 203 架战机，但是绝大多数准备不足，远水解不了诺门罕的近渴。
在双方空军部队磨刀霍霍之时，地面上的红星却已经渡过了哈勒哈欣河，还在东岸建立了坚固的桥头堡阵地，静等旭日章下的野兽们过来撞个头破血流，深感“皇军”面子被熊狠狠抓了一把的日本陆军，正在集结力量准备给苏联人一个大大教训，当然日后的战役发展证明，这个教训在天上或者地下，恰恰都是给日本人自己的。
日升日落
虽然地面作战打得有声有色，天上的红星却被旭日的光辉彻底遮蔽了光彩。在 5 月 28 日这一天，3 架 I-15Bis 在哈勒哈欣河上空撞见了一群日本战斗机，仗着人多始终，日本战斗机在几分钟内连中三元，上演了空中帽子戏法。
这一天晚些时候，又有十架 I-15Bis 被日机偷袭，18 架 Ki-27 躲在高空，看准目标后呼啸而下。苏联战机虽然奋起反击，怎奈高度和速度优势都不在自己一边，最终被击落六架，另有一架 I-15 勉强迫降，本以为逃过一劫，没想到日本人不依不饶，俯冲而下轮番扫射，最终将这架 I-15Bis 打成一堆火焰。侥幸生还的 I-15Bis 中还有两架严重受损，只能在最近的前线机场迫降，落地后便报废了。而打得苏军只剩一架全身而退的日本人自己却是毫发无损。
看着空中的红星逐渐暗淡，红军的高级将领也是心急如焚，尼古拉.凡克尼科夫 （Nikolai Feklenko，始终混不上去的倒霉蛋，卫国战争中多次被撤换，42 年到 43 年打得最激烈的时候被送去后方当了坦克装甲车训练中心主管）红军第 57 特别军（the 57th Special Corps，日苏开始在满蒙边境发生摩擦后，后贝加尔军区派往蒙古的部队）司令亲自上书莫斯科报告日本航空部队在诺门罕上空占尽优势、横行无忌。结果，6 月 2 日他以“丧失战斗意志”的理由被撤换，继任者朱可夫上任伊始便着手将士气低落的部队改编为第一集团军（the 1st Army Group，但是在苏联军事编制中，这个等级应该是“Front”）。
Nikolai Feklenko
实际上，莫斯科早就对苏联空军在诺门罕的糟糕表现有所耳闻，也已经计划好如何扭转颓势。与新任司令员一同抵达蒙古的还有大批参加过西班牙内战和苏联援华支援航空队的资深飞行尖子。针对之前驻蒙古的苏联空军部队机构臃肿，指挥体系混乱的问题，莫斯科将西班牙战场上的飞将军雅科夫.斯穆什克维奇（Yakov Smushkevich，日后的空军元帅）调到蒙古，将整个航空部队交由他全权指挥。
雅科夫.斯穆什克维奇 Yakov Smushkevich，两次苏联英雄，未来的空军元帅
1938 年雅科夫的座机
在精兵强将齐集哈勒哈欣河的同时，大批新式战机也从苏联各地汇聚而来。1939 年 6 月 21 日，诺门罕上空的空军力量天平已经毋庸置疑倒向苏联这边：301 架红星战机和他们士气高涨磨拳擦掌的驾驶员时刻准备着痛殴河对面后劲不足的日本鬼子，后者手里战机只有区区 126 架，还不到苏军的一半。
1989 年版蒙古地图
仗打到这个时候，苏日双方都明白谁占有空中优势，谁就更可能取得最终的全面胜利。当苏日双方都已经再也挤不出哪怕一架的增援时，所有人都清楚，6 月22 日开始的殊死拼杀将决定最终是红星和旭日谁将闪耀哈勒哈欣河上空。这一天，苏联人派出了 56 架 I-16 和 49 架 I-15Bis 组成的庞大机群，日本方面则声称有超过 100 架日本战机参与了当天的空战，但大家想象中的一锤定音并没有出现，结果接下来的几天，100 多架战机的大规模混战成了诺门罕上空的家常便饭。