A sus 16 años, en 1929, Heinlein emprendió viaje a Alemania con la intención de inscribirse en el Bachillerato para ingresar a la carrera de Música en el Conservatorio Stern (Sternsches Konservatorium), con los profesores de teoría, armonía y orquestación Wilheim Klatte y Paul Graener. Allí fue compañero de Claudio Arrau, quien ya era un alumno destacado. Paralelamente, estudió en la Universidad Friedrich Wilhelm de Berlín la carrera de Musicología con los profesores Arnold Schering y Friedrich Blume. Este período de formación se extendió hasta 1934.

En 1949, establecido ya en Chile, realizó un viaje a Inglaterra para perfeccionarse en la Escuela de Verano de Blandford, donde estudió composición con Nadia Boulanger, clavecín y clavicordio con Thurston Dart y pedagogía del piano con Anthony Hopkins.