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