Coronary artery disease is a major problem worldwide causing 7.2 million deaths worldwide annually, resulting from vascular occlusion, myocardial infarction and its complications. Stent implantation is a percutaneous interventional procedure that mitigates vessel stenosis, providing mechanical support within the artery. 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 Focussed Ion-Beam (FIB) milling offers several advantages for flexible prototyping (i) practically any substrate material that is able to withstand high vacuum conditions of the microscope chamber can be used, (ii) there is high flexibility in the obtainable shapes and geometries by modulating the ion beam current and the patterning conditions, (iii) reduced complexity of the pattering process e.g. it is a single-step process with a possibility of real-time monitoring of the milling progression. On the other hand FIB patterning of polycrystalline metals is greatly influenced by channelling 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 report we present a FIB patterning protocol for nano-structuring features (concaves) ordered in rectangular arrays on pre-polished 316L Stainless Steel (SS) 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 (SEM), Electron Backscattered Diffraction (EBSD), and Atomic Force Microscopy (AFM).Various dose 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.