Critical (software) systems are all around us. These systems are typically characterised by stringent dependability requirements and demand elevated levels of robustness and fault tolerance. To assure that they function as intended and provide a number of quality guarantees, formal methods and automated verification techniques and tools have been in use in the engineering of such critical systems for many years now. In this introduction to the special issue FMICS-AVoCS on "Formal Methods and Automated Verification of Critical Systems", we outline a number of recent achievements concerning the use of formal methods and automated verification techniques and tools for the specification and analysis of critical systems from a variety of application domains. These achievements are represented by six selected papers: five were selected from the joint 21st International Workshop on Formal Methods for Industrial Critical Systems and 16th International Workshop on Automated Verification of Critical Systems (FMICS-AVoCS 2016), while one of them was selected after an open call for papers.