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

وظلت هذه القضية في باريس أكثر من ثلاث سنوات من سن (1269-1273)، وخير الدين فيها يرافع ويدافع، وابن عياد يملأ فرنسا دويا، ويساعده على ذلك ما ينفقه عن سعة ويشتري الدور والأملاك في فرنسا، وعلى خير الدين أن يقاوم كل هذا.

وأخيرا كلفت لجنة القضايا بوزارة الخارجية الفرنسية دراسة هذا الخلاف ورفع تقرير عنه، وشكلت لجنة تحكيم يرأسها الإمبراطور نابليون الثالث، وأصدرت حكمها وهو يقضي بتخفيض مطالب ابن عياد من ستين مليون قرش إلى خمسة ملايين، كما ألزمته بأن يدفع للحكومة التونسية 14 مليون قرش في ذمته لها، ودفع مبالغ أخرى، فكان مكسب تونس من هذه القضية نحو 24 مليون فرنك. وفوق ذلك قام خير الدين في هذه السفرة بأعمال أخرى، أهمها أنه لما حدثت حرب القرم (1270ه / 1853م) أرسل الباي أحمد لمساعدة الدولة العثمانية 14 ألف جندي بأدواتهم الحربية وأسطولا من سبع قطع، وهذا أثقل كاهل تونس، فأرسل الباي إلى خير الدين بباريس مجوهرات لبيعها وفوضه في أمر ثمنها، فلم يقبل خير الدين هذا التفويض، وظل يراجع الباي فيما يعرض من ثمن حتى أنكر عليه كثرة الاستشارة وأمره بالبيع فورا فباع.

ولم يكف ثمن هذه المجوهرات، فكلفه الباي أن يعقد قرضا من فرنسا، وكانت هذه مسألة خطيرة لم يستطع ضمير خير الدين أن يحتملها؛ لا سيما وأن الباي قد أصيب بالشلل وقربت منيته، فماطل وماطل، وأخذ يبعث بالاستفهام تلو الاستفهام حتى مات الباي ولم يتم عقد القرض، فكانت محمدة من محامده حمدها له أهل تونس والباي الجديد المشير محمد باشا، وأنعم عليه برتبة فريق سنة (1272).

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

ومما يؤسف له أنه بعد هذه الفضائح كلها بقي مصطفى خزنه دار، المغتصب الكبير وصهر خير الدين في منصبه في الوزارة.

عاد خير الدين إلى تونس فعينه الباي محمد باشا وزيرا للحربية سنة (1273)، وظل في هذا المنصب إلى سنة (1279)، وفي هذه الفترة قام بإصلاحات كثيرة، فأصلح ميناء «حلق الوادي» وهو أعظم ميناء لتونس، وأمر بأن يقيد كل شيء في وزارته، وكان هذا النظام أول ما أدخل في تونس.

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

وصدر الأمر به سنة (1277)، وانتخب أعضاء المجلس، وكان خير الدين الرئيس الفعلي له بجانب وزارته للحربية.

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