The rate of star formation both in the Galaxy and in external galaxies should be related to the physical properties of the molecular clouds from which stars form. This is expected for the starbursts found both in irregular galaxies and in some mergers. The dwarf galaxy Henize 2-10 is particularly interesting in this context as it shows a number of newly formed Super Star Clusters (SSCs) associated with a very rich molecular environment. We present a high angular resolution study of the molecular gas associated with the SSCs with the aim of deriving the physical properties of the parent molecular clouds. The final goal is to test the expectation that the formation of SSCs requires exceptionally dense and massive clouds. We have used the Submillimeter Array with an angular resolution of 1.9 X 1.3 to map the J=2-1 transition of CO in Henize 2-10. Supplementary measurements of HCN(J=1-0), 13CO(J=2-1) and millimeter continuum were obtained with the APEX, IRAM-30m and SEST single dish telescopes. Our single dish observations confirm the association of the newly formed SSCs in Henize 2-10 with dense molecular gas. Our interferometric observations resolve the CO(2-1) emission in several giant molecular clouds. Overall the molecular gas accounts for approximately half of the mass in the central regions of Henize 2-10. Although we find indications that the molecular clouds associated with the formation of SSCs in Henize 2-10 are massive and dense, the tracer we used (CO) and the linear resolution of our observations (60 X 80 pc) are still not adequate to test the expectation that exceptionally dense and massive cores are required for SSCs formation.