Stent implantation is a percutaneous interventional procedure that mitigates vessel stenosis, providing mechanical support within the artery and as such a very valuable tool in the fight against coronary artery disease. However, stenting causes physical damage to the arterial wall. It is well accepted that a valuable route to reduce in-stent re-stenosis can be based on promoting cell response to nano-structured stainless steel (SS) surfaces such as, for example, by patterning nano-pits in SS. In this regard patterning by Focused Ion-Beam (FIB) milling offers several advantages for flexible prototyping. On the other hand FIB patterning of polycrystalline metals is greatly influenced by channeling effects and re-deposition. Correlative microscopy methods present an opportunity to study such effects comprehensively and derive structure-property understanding that is important for developing improved pattering. In this chapter we present a FIB patterning protocol for nano-structuring features (concaves) ordered in rectangular arrays on pre-polished 316L stainless steel surfaces. An investigation based on correlative microscopy approach of the size, shape and depth of the developed arrays in relation to the crystal orientation of the underlying SS domains, is presented. The correlative microscopy protocol is based on cross-correlation of top-view Scanning Electron Microscopy, Electron Backscattering Diffraction, Atomic Force Microscopy and cross-sectional (serial) sectioning. Various FIB tests were performed, aiming at improved productivity by preserving nano-size accuracy of the patterned process. The optimal FIB patterning conditions for achieving reasonably high throughput (patterned rate of about 0.03 mm2 per hour) and nano-size accuracy in dimensions and shapes of the features, are discussed as well.