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