Aluminum nanostructures are a promising alternative material to noble metal nanostructures for several photonic and catalytic applications, but their ultrafast electron dynamics remain elusive. Here, we combine single-particle transient extinction spectroscopy and parameter-free first-principles calculations to investigate the non-equilibrium carrier dynamics in aluminum nanostructures. Unlike gold nanostructures, we find the sub-picosecond optical response of lithographically fabricated aluminum nanodisks to be more sensitive to the lattice temperature than the electron temperature. We assign the rise in the transient transmission to electron–phonon coupling with a pump-power-independent lifetime of 500 ± 100 fs and theoretically confirm this strong electron–phonon coupling behavior. We also measure electron–phonon lifetimes in chemically synthesized aluminum nanocrystals and find them to be even longer (1.0 ± 0.1 ps) than for the nanodisks. We also observe a rise and decay in the transient transmissions with amplitudes that scale with the surface-to-volume ratio of the aluminum nanodisks, implying a possible hot carrier trapping and detrapping at the native oxide shell–metal core interface.