但成吉思汗并不想用二十万大军进攻一座边城，当全军集中后，他立刻分兵四路，分头前进：第一路由察合台、窝阔台率领，留攻讹答剌城；第二路由术赤率领向毡的和养吉干进军；第三路由若干将领率领，向忽毡和别纳客忒方向进军。他们的任务是从左右两翼攻取锡尔河畔的各个城市，扫荡花剌子模的边界。第四路即成吉思汗的中军，由成吉思汗及其幼子拖雷率领，直指不花刺城。花刺子模的新都撒麻耳干在不花刺以东，旧都玉龙杰赤在不花刺西北。国王驻新都，母后秃儿罕哈敦驻旧都。成占思汗首战的目标是攻取讹答剌等边界城市，自率中军进攻不花剌，目的在于避实击虚，从中间突破，切断花剌子模新旧二都之间的联系。
留攻讹答刺的蒙古军队从四面八方攻城，守军也顽强不屈，一次又一次打退了蒙古军队的进攻，双方在讹答刺厮杀了5个月。最后，讹答刺军民陷入绝境，援军将领哈剌察建议海儿汗向蒙古投降，把城市献给蒙古人，但海儿汗十分清楚，他是这场战乱的肇祸人，他不能指望蒙古人浇他不死。蒙古人将讹答刺城包围得水泄不通，海儿汗也没有逃生之路，因此他主张竭尽全力继续战斗，不同意缔结和约。
哈刺察见海儿汗不肯投降，也不便深劝。为了保全性命，他当天夜里就率领本部人马离开了讹答刺城，企图溜之大吉。蒙古军抓住了他，将他带去见察合台、窝阔台二王。察合台、窝阔台对他进行了审讯，从他嘴里了解了城内守军的情况，然后向哈刺察及其部下宣布：“你们不忠于自己的主子，尽管由于过去的恩惠，他要求你们忠于他。因此，我们也不能指望你们的效忠。”为了维护主奴关系和君臣关系，察合台、窝阔台下令把这批动摇变节的人统统杀掉了。
随后不久，蒙军攻下了讹答刺城，城里的百姓像绵羊一样全部被赶出城，蒙古人则大肆劫掠。海儿汗率领两万名好汉和勇士退守内堡，决定进行殊死的反抗。他们视死如归，在互相诀别后，一次冲出五十人，拿身子去拼刀枪。察合台、窝阔台下令活捉海儿汗，不要在战斗中杀死他。蒙古军将士遵守这一命令，这反倒给海儿汗提供了坚持战斗的机会。最后只剩下他一个人了，察合台、窝阔台将他俘获送给成吉思汗处理。后来成吉思汗在撒麻耳干郊外的离宫阔克撒莱用熔化的银液灌进他的耳朵和眼睛，以示对贪财者的惩罚，为被杀害的商人报仇。
讹答剌的内堡和城池被夷为平川，然后蒙古人离开。从此，这座锡尔河的历史名城变成了一片废墟。
皇子术赤是负责进攻毡的和养吉干的蒙军统帅。术赤的军队首先来到毡的州内、位于锡尔河畔的速格纳黑城。此城又译作“昔格纳黑”，其遗址今名苏纳克库尔干，在今哈萨克图门阿鲁克邮站以北十八公里处。他派哈散哈只带一个使团去招谕速格纳黑城居民。“哈散哈只”又译“忽辛·哈只”，即在班朱尼湖畔投靠成吉思汗的花刺子模商人哈散纳。因为哈散哈只，与当地人相熟，又是他们的同胞，术赤便命他去劝告这一带的居民不要进行抵抗。号召他们投降，让他们保全生命财产。但当他前往速格纳黑时，他刚刚传达完自己的使命，还没有来得及以同胞的身份提出劝告，一些城民就杀死了他。术赤得知这一消息后，怒火中烧，他命士卒从早到晚轮番作战。军士奉命连攻七天，袭取了速格纳黑城。术赤将这个地区交给被杀死的哈散哈只的儿子管辖，让他去召集仍在穷乡僻壤的残存者。
蒙军从该地继续前进，攻占了位于锡尔河下游、速格纳黑与毡的之间的两座城市讹迹邗和巴耳赤邗。由于那里的百姓没有进行大规模的抵抗，所以蒙军也没有实行大屠杀。
有关这些战事的消息传到毡的，摩诃末派去防守那个地区的最高统将忽都鲁汗如惊弓之鸟，三十六计走为上，他乘夜间渡过锡尔河，横越沙漠地带，跑到花刺子模旧都玉龙杰赤去了。守将和军队的逃走为术赤和平占领毡的创造了条件，为此他派成帖木儿带着使团到毡的去招降居民，劝他们停止敌对行动。
1220年4月21日，术赤兵临毡的城下。将士们迅速填塞城壕，架设撞城器、射石机和云梯。城内的居民，除紧闭城门，像节日的观众那样坐在城头和城垛上外，没有做战斗准备。因为大部分市民从来没有战争经验，他们对蒙古人的活动感到惊讶，当蒙古人造好桥，架上云梯发动攻击时，毡的人才被迫投入战斗。他们怀着恐惧心情去发动一架投石机，但由于他们不了解投石机的使用方法，发射出的石块不是飞向敌人，而是落在了地面，恰好砸碎了那台投石机的铁环。正当城头的百姓们乱作一团时，蒙古人已从四面八方爬上了城墙，很快就打开了城门，大队蒙古兵开入毡的城中。双方无一人伤亡。蒙军把居民赶到城外，他们强迫居民在郊外停留九天九夜，蒙军将士则在城内劫掠。然后，他们派阿里火者管理毡的。阿里火者出身于不花剌的下层土著，早在成吉思汗兴起之前就归附了成吉思汗，后来又作为第一次出使花刺子模的使团首领之一见到了摩诃末。
随后，术赤派一名将官分兵攻下邻近城市养吉干。“养吉干”，突厥语犹言新城。它位于锡尔河南，距花剌子模湖（咸海）二日程，距卡扎林斯克约十五英里。他们在那里留下了一名长官（沙黑纳），负责管理养吉干事务。
成吉思汗派出的扫清花刺子模边界的第三路军开始只有五千人，统率这支军队的是三员战将。他们是中军万户纳牙阿的兄弟阿剌黑，成吉思汗八十八功臣之一的速客秃，即《蒙古秘史》上所说的雪亦客秃；以及与雪亦客秃一起投靠成吉思汗的、速勒都思族人塔孩。他们都是成吉思汗的著名功臣，在历次战争中屡立战功。他们进攻的第一个目标是费纳客忒。费纳客忒守将名叫亦列惕古灭里，他带领一支突厥、康里军队同蒙古人厮杀了三天，蒙古军毫无进展。但到第四天，城民请求赦免，他们自动走出城来，纳款投降。
然后蒙古人向忽毡进发，当他们兵临城下时，居民躲进了内堡，企图逃脱噩运的残害。城堡的守将是花刺子模的民族英雄帖木儿灭里，这个城堡修在锡尔河中央、河水分为两股的地方。城堡高大、坚固，由帖木儿灭里率领几千名骁勇的士卒和著名的武士驻守堡内。蒙古军队到来后，发现河中央的城堡在箭和弩炮的射程之外，不可能很快攻下。于是他们把忽毡的青年男子强行编入哈沙儿队，又从讹答刺所占城、乡调来五万哈沙儿队、两万蒙古兵助战。他们从三程远的山中将石头运来，填人锡尔河中，企图逐步接近城堡。
帖木儿灭里造了十二艘密封的战船，船上蒙一层湿毡，外涂一层揉有醋的黏土，上面留有若干窗口作为射箭之用。每天拂晓，他派六艘这样的船，向一方驶去，与蒙古军激战。无论是箭、火、石油对这些战船都失去了效用。蒙古人投入河中的石头，也被他们抛到岸上。夜里他们向蒙古军发动突袭，搞得蒙古军疲惫不堪。后来，蒙古军准备了许多箭和弩炮进行激战。帖木儿灭里势渐不支，便于夜里装备了七十只船，准备逃跑。船上装载了伤员、辎重和财物器用，他自己则率领一队战士登上一艘大艇，点燃火把，闪电般飞速沿河而下。蒙古军沿着河岸赶来，每逢成群的蒙古军出现时，帖木儿灭里就把他的战艇飞快地驶去，射箭驱逐他们，矢无虚发，一直到达别纳克忒。蒙古军为了阻止他前进，拦河拉起了几条铁链。帖木儿灭里无畏地冲在前面，砍断了那些铁链。在他到达毡的和巴耳赤邗境内之前，两岸的蒙古军一直和他作战。术赤接到有关帖木儿灭里的情报后，立即沿着锡尔河两岸布置了兵力，结舟为桥，备好了弩炮，准备将这支顽抗的敌军消灭在锡尔河中。
帖木儿灭里得知蒙古军设伏的消息后，当接近巴耳赤邗时即舍舟上岸，骑上快马，如火一样飞驰。蒙古军尾随不放，紧紧追赶。于是帖木儿灭里打发辎重先行，亲自殿后厮杀。他多次挥刀舞剑冲入蒙古军队中，待辎重走远了，他才设法摆脱敌人，重新追上队伍。
他就这样与蒙古军厮杀了几天，人马伤亡过半，蒙古军却越来越多。后来，他的辎重被蒙古人夺走了，他手下的人也所剩无几了，但他依然倔强不降。当随身的几人战死后，他也丢掉了武器，只剩下了三支箭，其中还有一支无头的断箭。这时，三个蒙古骑兵追到他身后，他用那支无镞箭射瞎了一个蒙古人的眼睛，对另外两个蒙古人说：“我还剩两支箭，舍不得用，却刚够你们两位消受。你们最好退回去，保全你们的性命。”这两个蒙古人目睹了帖木儿灭里的箭法，为了保全自己的性命，只好放帖木儿火里逃走了。
帖木儿灭里对蒙古军的英勇抵抗，是成吉思汗西征后所遇到的第一次硬仗。他以区区几千人马对付蒙古的两路大军，这说明在花剌子模军队中也有一些英勇善战、不甘屈服的将领和勇士。
当成吉思汗派出的三支部队扫荡花剌子模边界各城时，他和拖雷则率领中军向不花刺进发。他们沿锡尔河东岸前进，首先来到匝儿讷黑城下。这是锡尔河左岸的一个堡寨，其废墟在今卡拉库尔湖附近，是从讹答剌通往不花刺、撒麻耳干的第一座城堡。这里的人民虽然有意进行抵抗，但却失掉了抵抗的勇气。根据一贯的做法，对于不进行武力反抗的城市，成吉思汗还是先礼后兵，于是他派答失蛮哈只卜为使者，到他们那里去通知蒙古军的到来，劝他们投降，希望他们避免一场可怕的灾祸。
哈只人建议投降，于是他们立即去拜见成吉思汗，成吉思汗发现他们真心投诚，这才免他们死罪，和颜悦色地抚慰他们。然后，成吉思汗发下一份沼书，要求所有城民都到郊外去，城墙和护城河被夷为平地，青壮年被征发到“哈沙儿”队中，余下的人则听任他们回家。由于这座城没有遭到屠杀，人们给它取名为“忽都鲁八里”，即“幸福城”。
离开这座“幸福城”后，成吉思汗派晃豁坛氏的塔亦儿（答亦儿）巴特儿为前锋，给主力军开道。当地有个突厥蛮向导，很熟悉大道小径，他领蒙古人走了一条很少有人走的道路，使蒙古人很快进人讷儿境内。从此，这条由“幸福城”通往讷儿城的近路就被称为“汗之路”。
当蒙军接近讷儿城时，途经几座园林。他们在夜间伐木为梯，第二天骑着马，抬着梯子，行军异常缓慢。讷儿城头上的守望者以为他们是商旅，眼看着他们直抵讷儿城下，这才紧闭城门。经过使者多次往返，双方达成了如下协议：讷儿人将粮草进献给成吉思汗，借此表示已向他臣服；塔亦儿的军队则不开入城中，继续前进。
当讷儿人将粮草献给成吉思汗时，成吉思汗下令将该城交给正在率领前锋逼近讷儿的速不台。讷儿人不敢违抗，遵命交出了城池，随后双方又达成一条协议：应免去讷儿人的危难，允许他们保留日常生活、从事农耕的所需之物，如牛羊等；讷儿人则暂时搬到城外，原封不动地留下屋舍，任凭蒙古军队抄掠。速不台的军队进城后，见什么就拿走什么，但他们遵守协议，丝毫没有伤害讷儿人。于是讷儿人选出六十人作为城民的代表，跟随蒙古军队去进攻另一座城市。
后来，成吉思汗的中军到达讷儿城，居民前去迎接他，并进献了各种礼物。成吉思汗也对他们优礼相待，只让他们交纳应向摩诃末算端承担的赋税，不再向他们多征。为了满足成吉思汗的要求，讷儿人尽量搜集金钱，包括妇女的耳饰，如数交给了成吉思汗。讷儿人通过机智的谈判，虽然在经济上受到很大损失，但却应付了蒙古的三支大军，免除了杀掠之苦，解脱了鞑靼人的束缚和奴役之辱。当然，由于它的不抵抗政策，也使蒙古军队大大提高了进军速度，迅速加重了不花剌和首都的军事压力。
1220年3月至4月初，成吉思汗的中军进至不花剌城下。不花剌即今乌兹别克斯坦的布哈剌，它位于河中地区的阿姆河东岸，除撒麻耳千外，它是当地最重要的城市，中亚封建时代最大的文明和宗教中心。
《世界征服者史》和《史集》比较详细地记载了成吉思汗夺取不花刺的情况。《世界征服者史》说：“成吉思汗把国王的营盘扎在城池前的郊野。他的军队多如蚂蚁、蝗虫，数都数不清。人马一支接一支抵达，就像大海起伏，绕城扎营”。当时，不花刺共有守军二万人，他们的统将是阔克汗、哈迷的布尔、舍云治汗、怯失力汗等。巴尔托德《突厥史》认为，“阔克汗”即“菊儿汗”，这不是别人，而是成吉思汗的老对头札木合。志费尼则说：“据说阔克汗是名蒙古人，从成吉思汗那里逃奔算端（这话得由说的人证明）”估计他是被成吉思汗打败的一个蒙古草原贵族，但绝不会是札木合，具体是哪个部落的首领已不得而知。“哈迷的布尔”《史集》写作“哈迷忒·普儿·塔阳古”，他是一个哈刺契丹人。“怯失力汗”，《史集》作“古失鲁汗”，他本是摩诃末算端的马夫，后成为花刺子模的大总管，不花剌城的长官。摩诃末将自己的亲信和富于作战经验的将领放在不花刺，足见其对不花刺的重视。但不花剌的诸位将领和两万守军却辜负了算端的厚望，他们一见蒙古骑兵堵塞了四郊，城外尘土飞扬，天昏地暗，一个个惊恐万状，吓得要命。他们互相传诵一句所谓真主的预言：“在呼罗珊有条叫做乌浒水（阿姆河）的河流以东，将有一座城池被征服；该城叫不花剌。”这种宗教的预言没有给守军带来力量，反而为他们弃城逃跑提供了充分的根据。蒙古军陆续攻城数日，守城诸将支持不住，在拂晓时，率军出走。不久之后，当蒙古军正在营中熟睡，借以恢复连日作战的疲劳时。不花剌人向蒙古军队发动了突袭，面对这种突如其来的袭击，蒙古军队慌忙撤退。但是花刺子模军并没有乘胜追击，反而是逃走了。他们大概在想：反正真主的使徒说了，不花刺要被征服。蒙古军队很快从慌乱中清醒过来，收集队伍，随后追击，在阿姆河岸边追上了逃军，把他们斩杀殆尽。
