القوطيون ملوك الأندلس، فزحف طارق إليه، فاقتتلوا قتالًا شديدًا، وفتح الأندلس ثم خرج موسى بن نصير إلى البلد، وكان قد غضب على طارق مولاه في أمور بلغته عنه، فلقيه طارق، فترضاه، فرضي عنه، ووجهه إلى مدينة طليطلة، وهي من عظام مدائن الأندلس، على مسيرة عشرين يومًا، فأصاب فيها مائدة ذهب مفصصة بالجوهر، قيل إنها مائدة سليمان بن داود، فكسر رجلها، فأخذها، وبعث بها إلى موسى بن نصير. وكان الحجاج قد عزل يزيد بن المهلب عن خراسان، وولي المفضل، فأقر المفضل ثم عزله وولى قتيبة بن مسلم الباهلي، وكان قتيبة عامله على الري، وكتب إليه أن يستوثق من المفضل وبني أبيه، ويشخصهم إليه، فسار قتيبة من الري حتى قدم مرو، فأخذ المفضل بن المهلب وسائر ولد المهلب، فأشخصهم إلى الحجاج، فحبسهم وطالبهم بستة آلاف ألف.

وصار قتيبة إلى بخارى، فافتتحها، وافتتح عدة مدن منها، ثم انصرف وخلف فيها ورقاء بن نصر الباهلي، وأمره بقبض الصلح. وكان نيزك صاحب الترك قد صار إلى قتيبة، فلم يزل معه يحضر حروبه، فلما انصرف قتيبة تحرك طرخون صاحب السغد وجيل أبو شوكر بخار أخداه، وكر معانون اللوفسي في الترك، فكره قتيبة قتالهم، فوجه حيان النبطي فصالحهم. ثم صار إلى الطالقان، وبها باذام قد عصى وتغلب على البلد، وكان ابن باذام مع قتيبة، فلما بلغه أن باذام قد تحصن وعصى وارتد أخذ ابنه، فقتله، وصلبه وجماعة معه، ثم لقي باذام فقاتله أيامًا، ثم ظفر به فقتله، وقتل ولده وامرأته، واستعمل على البلد أخاه عمرو بن مسلم.

ولما فتح قتيبة بخارى والطالقان استأذنه نيزك طرخان في الرجوع إلى بلاده، وكان نيزك قد أسلم وسمي بعبد الله، فأذن له، فرجع إلى طخارستان، فعصى، وكاتب الأعاجم، وجمع الجموع، فزحف إليه قتيبة، ووجه إليه سليما الناصح، وكان صديقا له، فلم يزل يختدعه ويعطيه عن قتيبة ما يسأل، حتى خرج إلى قتيبة على الأمان فأقام عنده أيامًا ثم ضرب عنقه وعنق ابن أخت له، وبعث برؤوسهما إلى الحجاج، وأخذ امرأة نيزك، فلما خلا بها قالت له: ما أجهلك! أظننت أن نفسي تطيب لك، وقد قتلت زوجي وسلبتني ملكي؟ فخلاها، وقال: اذهبي حيث شئت.

ثم سار قتيبة إلى السغد، فلقيه صاحب السغد، فصافه أيامًا، ثم هرب منه، ولحق قتيبة الشتاء، فانصرف وكتب إليه الحجاج يأمره بالمصير إلى سجستان ومحاربة رتبيل، فسار سنة اثنان وتسعون، حتى صار إلى زالق من أرض سجستان، ثم زحف إلى رتبيل، فوجه إليه رتبيل: أنا كنا قد صالحناكم، وقبلتم الصلح، فما ذا دعاكم إلى نقضه؟ فأرسل إليه أن الحجاج أبي ذلك، فرد عليه رتبيل: إن قبلتم الصلح كان أصلح لكم، وإلا رجونا النصر عليكم. فقال قتيبة لأصحابه: إن هذا وجه مشؤوم، وقد هلك فيه عبد الله بن أمية، وابن أبي بكرة، وغير واحد، ولا نأمن الحيل التي كان رتبيل يحتالها من تحريق الطعام، والعلوفات، وأخذ الحصون والسهل وحمل ما... فولى قتيبة عبد ربه بن عبد الله بن عمير الليثي، وسار قتيبة إلى خوارزم، وبها سعيد بن ونوفار، وكانوا قتلوا عامل قتيبة، فقدمها، فسبى مائة ألف، وحاصر سعيد بن ونوفار حتى قتله.

فلما أصلح البلاد وانصرف بالغنائم التي لم يسمع بمثلها، وأراد جنده الرجوع إلى أوطانهم بما في أيديهم، قام قتيبة خطيبا، فذكرهم ما كانوا فيه، وأعلمهم أنه لا براح لهم، واستخلف على خوارزم عبد الله بن أبي عبد الله الكرماني، ثم سار قتيبة إلى سمرقند، وكان غوزك قد قتل طرخون ملك السغد، وتملك على البلد، فلما وافى قتيبة حاربه، فكانت بينهم حروب شديدة، وأحب قتيبة الصلح فراسل غوزك يدعوه إلى ذلك، فقال لأهل سمرقند: علام نصالحهم، وبلدنا لا يدخله إلا رجلان: إما أحدهما فقيل وإما الآخر فاسمه إكاف، فكبر قتيبة، وكبر المسلمون، وقالوا: أميرنا اسمه قتب البعير، فأذعنوا بالصلح على أن يدخل فيصلي ركعتين، فدخل من باب كش، وخرج من باب الصين، واتخذ لهم غوزك ملك سمرقند الطعام، فأكل قتيبة وأصحابه، فكتب له كتاب صلح: هذا ما صالح عليه قتيبة بن مسلم غوزك إخشيد السغد، أفشين سمرقند على السغد، وسمرقند وكش، وكسف، صالحه على ثلاثة آلاف درهم يؤديها غوزك إلى رأس كل سنة، وجعل له عهد الله وذمته، وذمة الأمير الحجاج بن يوسف، وأشهد له شهودا، وكان ذلك سنة أربع وتسعون.