ولم يغفل عبد الرحمن في الوقت الذي كانت فيه ثورة ابن حفصون وأبنائه في جنوب الأندلس، تشغل معظم عنايته، عن مطاردة الثورة في الأنحاء الأخرى.
وكانت طليطلة من أمنع معاقل الثورة، فسير عبد الرحمن جنده لحصارها، وفيها لُبّ بن الطربيشة وهو من زعماء المولدين، واستمر الحصار زهاء عامين حتى نضبت موارد المدينة، وخبت عزائم أهلها واضطرت في النهاية إلى التسليم والإذعان.
وسار لبّ مع الأمير بقواته إلى الغزو في أرض النصارى (سنة ٣٠٨ هـ). وكانت بطليوس وأحوازها منذ أكثر من أربعين عاماً، معقلا من معاقل ثورة المولدين.
وكان بنو مروان الجليقي ما يزالون يسيطرون على تلك المنطقة، وكانوا من أخطر الخوارج وأشدهم مراساً، يمالئون الأمراء النصارى ويحالفونهم على حكومة قرطبة.
ففي سنة ٣١١ هـ (٩٢٣ م)، هلك عبد الله بن محمد بن مروان الجليقي صاحب بطليوس قتيلا بيد بعض المخالفين من أصحابه، فقام مكانه ولده عبد الرحمن، واستبد بمدينة بطليوس وما حولها، واستمر بضعة أعوام على خروجه وتحديه لحكومة قرطبة.
وفي ربيع الأول سنة ٣١٧ هـ (إبريل ٩٢٩ م) خرج الناصر من قرطبة متجهاً نحو الغرب، ومعه ولداه الحكم والمنذر وعدة من الوزارء، واستخلف على القصر ولده عبد العزيز. وبعث الناصر ينذر المتخلفين عن الطاعة، بوجوب الدخول في طاعته، والتخلي عن العصيان، وفي مقدمتهم. صاحب بطليوس عبد الرحمن بن عبد الله الجليقي. ووصل الناصر بجيشه إلى بطليوس في أواخر ربيع الآخر من هذه السنة وحاصر بطليوس، وقاتل المتصدين للمقاومة حتى هزموا واقتحم أرباضهم، وأحرقت ديارهم، فامتنعوا داخل المدينة؛ فعهد الناصر بقتالهم إلى القائد أحمد بن إسحق القرشي في قوة كثيفة، فشدد في حصار المدينة، واقتحم ما حولها من الحصون، ثم ضربها بالمجانيق بشدة، وقطع عنها كل مورد، واشتد بأهلها الضيق، واضطر الجليقي إلى الإذعان وطلب الأمان، فأجابه الناصر إليه، وأسكنه هو وأهله وأكابر رجاله بحضرة قرطبة، وعين لبطليوس والياً جديداً هو عثمان بن عبد الله، وكان خضوع بطليوس في سنة ٣١٨ هـ (٩٣٠ م).
ولما غادر الناصر بطليوس سار إلى مدينة باجة، أقصى قواعد الغرب،