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

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