In this paper, we present a novel ultra thin Artificial Magnetic Conductor (AMC) intended for flexible and conformal applications. The proposed AMC is based on a magneto dielectric substrate which consists of a Cobalt nano-wire magnetic material deposited over a commercially available flexible dielectric substrate. As a benchmark, a square patch based AMC unit cell with an overall thickness of 1 mm is designed to have a reflection phase at 2.45 GHz. The inductance enhancement achieved by the magnetic material loading improves the bandwidth significantly compared to the considered low thickness. Our results show that a reduction of up to 10 times is achieved in terms of thickness when compared to conventional substrates which makes the proposed structure suitable for the targeted applications. Furthermore, the proposed structure offers a miniaturization of 4% which can be further increased if it is used with a higher permittivity material.