We report on the first use of laser ablation to make sub-millimeter, broad-band, anti-reflection coatings (ARC) based on sub-wavelength structures (SWS) on alumina and sapphire. We used a 515 nm laser to produce pyramid-shaped structures with pitch of about 320 $\mu$m and total height of near 800 $\mu$m. Transmission measurements between 70 and 140 GHz are in agreement with simulations using electromagnetic propagation software. The simulations indicate that SWS ARC with the fabricated shape should have a fractional bandwidth response of $\Delta \nu / \nu_{center}\ = 0.55$ centered on 235 GHz for which reflections are below 3%. Extension of the bandwidth to both lower and higher frequencies, between few tens of GHz and few THz, should be straightforward with appropriate adjustment of laser ablation parameters.