The full understanding of the deformation mechanisms in nanostructured bainite requires the local characterization of its mechanical properties, which are expected to change from one phase, bainitic ferrite, to another, austenite. This study becomes a challenging process due to the bainitic nanostructured nature and high Young’s modulus. In this work, we have carried out such study by means of the combination of AFM-based techniques, such as nanoindentation and Peak Force Quantitative Nanomechanical Mapping (PF-QNM) measurements. We have addressed critically the limits and advantages of these techniques and been able to measure some elastoplastic parameters of both phases. Specifically, we have analyzed by PF-QNM two nanostructured bainitic steels, with a finer and a coarser structure and found that both phases have a similar Young’s modulus.