Heller partit donc pour Paris, où il arriva dans le cours d'octobre 1838, avec une modique somme et sans autres ressources à espérer. Il alla voir Kalkbrenner, prit deux ou trois leçons de piano, mais fut bien vite obligé de les interrompre. Les conditions imposées par le professeur étaient singulières : payer 500 francs par an, rester cinq ans sous sa direction (cette direction consistait en un examen mensuel: il déléguait pour maître de piano un de ses élèves), — ne jamais rien publier sans son autorisation, de peur que l'élève ne compromît la renommée du maître.
Heller ne connaissait pas une note de Schumann ; il le prenait même pour un écrivain purement théorique et esthétique. Il entretint avec lui une correspondance qui ne cessa que peu d'années avant la maladie qui devait emporter le grand compositeur. Schumann se montra, pour le jeune Heller, plein de bienveillance; il lui prodigua les encouragements.