We demonstrate that a single-layer graphene replicates the shape of DNA origami nano structures very well. It can be employed as a protective layer for the enhancement of structural stability of DNA origami nano structures. Using the AFM based manipulation, we show that the normal force required to damage graphene encapsulated DNA origami nano structures is over an order of magnitude greater than for the unprotected ones. In addition, we show that graphene encapsulation offers protection to the DNA origami nano structures against prolonged exposure to deionized water, and multiple immersions. Through these results we demonstrate that graphene encapsulated DNA origami nano structures are strong enough to sustain various solution phase processing, lithography and transfer steps, thus extending the limits of DNA-mediated bottom-up fabrication.