Alumina ceramic, Al2O3, presents a challenge to laser micro-structuring due to its neglible linear absorption coefficient in the optical region coupled with its physical properties such as extremely high melting point and high thermal conductivity. In this work, we demonstrate clean micro-structuring of alumina using NIR (λ=775 nm) ultrafast optical pulses with 180 fs duration at 1kHz repetition rate. Sub-picosecond pulses can minimise thermal effects along with collateral damage when processing conditions are optimised, consequently, observed edge quality is excellent in this regime. We present results of changing micro-structure and morphology during ultrafast processing along with measured ablation rates and characteristics of developing surface relief. Initial crystalline phase (alpha Al2O3) is unaltered by femtosecond processing. Multi-pulse ablation threshold fluence Fth ~ 1.1 Jcm-2 and at low fluence ~ 3 Jcm-2, independent of machined depth, there appears to remain a ~ 2μm thick rapidly re-melted layer. On the other hand, micro-structuring at high fluence F ~ 21 Jcm-2 shows no evidence of melting and the machined surface is covered with a fine layer of debris, loosely attached. The nature of debris produced by femtosecond ablation has been investigated and consists mainly of alumina nanoparticles with diameters from 20 nm to 1 micron with average diameter ~ 300 nm. Electron diffraction shows these particles to be essentially single crystal in nature. By developing a holographic technique, we have demonstrated periodic micrometer level structuring on polished samples of this extremely hard material.