We demonstrate that a single-layer graphene replicates the shape of DNA origami nanostructures very well. It can be employed as a protective layer for the enhancement of structural stability of DNA origami nanostructures. Using the AFM based manipulation, we show that the normal force required to damage graphene encapsulated DNA origami nanostructures 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 nanostructures against prolonged exposure to deionized water, and multiple immersions. Through these results we demonstrate that graphene encapsulated DNA origami nanostructures are strong enough to sustain various solution phase processing, lithography and transfer steps, thus extending the limits of DNA-mediated bottom-up fabrication.