We investigate cosmological implications of an energy density contribution arising by elastic dark matter self-interactions. Its scaling behaviour shows that it can be the dominant energy contribution in the early universe. Constraints from primordial nucleosynthesis give an upper limit on the self-interaction strength which allows for the same strength as standard model strong interactions. Furthermore we explore the cosmological consequences of an early self-interaction dominated universe. Chemical dark matter decoupling requires that self-interacting dark matter particles are rather light (keV range) but we find that super-weak inelastic interactions are predicted by strong elastic dark matter self-interactions. Assuming a second, collisionless cold dark matter component, its natural decoupling scale exceeds the weak scale and is in accord with the electron and positron excess observed by PAMELA and Fermi-LAT. Structure formation analysis reveals a linear growing solution during self-interaction domination, enhancing structures up to ~ 10^(-3) solar masses long before the formation of the first stars.