We study the impact of Early Dark Energy fluctuations in the linear and non-linear regimes of structure formation. In these models the energy density of dark energy is non-negligible at high redshifts and the fluctuations in the dark energy component can have the same order of magnitude of dark matter fluctuations. Since two basic approximations usually taken in the standard scenario of quintessence models, that both dark energy density during the matter dominated period and dark energy fluctuations on small scales are negligible, are not valid in such models, we first study approximate analytical solutions for dark matter and dark energy perturbations in the linear regime. This study is helpful to find consistent initial conditions for the system of equations and to analytically understand the effects of Early Dark Energy and its fluctuations, which are also verified numerically. In the linear regime we compute the matter growth and variation of the gravitational potential associated with the Integrated Sachs-Wolf effect, showing that these observables present important modifications due to Early Dark Energy fluctuations, though making them more similar to $Lambda$CDM model. We also make use of the Spherical Collapse model to study the influence of Early Dark Energy fluctuations in the nonlinear regime of structure formation, especially on $delta_c$ parameter, and their contribution to the halo mass, which we show can be of the order of 10%. We finally compute how the number density of halos is modified in comparison to $Lambda$CDM model and address the problem of how to correct the mass function in order to take into account the contribution of clustered dark energy. We conclude that the inhomogeneous Early Dark Energy models are more similar to $Lambda$CDM model than its homogeneous counterparts.