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