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