પ્રારંભિક શિક્ષણ પૂર્ણ કર્યા પછી, શાહ નવાઝ લશ્કરી તાલીમ મેળવી અને ૧૯૩૫ માં બ્રિટીશ ભારતીય સૈન્યમાં જોડાયા.