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