Superluminous supernovae (SLSNe) are very bright explosions that were only discovered recently and that show a preference for occurring in faint dwarf galaxies. Understanding why stellar evolution yields different types of stellar explosions in these environments is fundamental in order to both uncover the elusive progenitors of SLSNe and to study star formation in dwarf galaxies. In this paper, we present the first results of our project to study SUperluminous Supernova Host galaxIES, focusing on the sample for which we have obtained spectroscopy. We show that SLSNe-I and SLSNe-R (hydrogen-poor) often (~50% in our sample) occur in a class of galaxies that is known as Extreme Emission Line Galaxies (EELGs). The probability of this happening by chance is negligible and we therefore conclude that the extreme environmental conditions and the SLSN phenomenon are related. In contrast, SLSNe-II (hydrogen-rich) occur in more massive, more metal-rich galaxies with softer radiation fields. Therefore, if SLSNe-II constitute a uniform class, their progenitor systems are likely different from those of H-poor SLSNe. Gamma-ray bursts (GRBs) are, on average, not found in as extreme environments as H-poor SLSNe. We propose that H-poor SLSNe result from the very first stars exploding in a starburst, even earlier than GRBs. This might indicate a bottom-light initial mass function in these systems. SLSNe present a novel method of selecting candidate EELGs independent of their luminosity. ; Comment: Published version, matches proofs. Accepted 2015 February 13. 23 pages, 8 figures, 4 tables. Minor changes with respect to previous version