Smart cities are the expected result of the intensive use of Information and Communication Technologies (ICT) in our daily life. They are the culmination of the great progress that has been made in ICT in the last few years. Smart cities aim to efficiently, sustainably, securely, and reliably manage critical infrastructures such as power systems, transportation, water systems, etc., for the sake of mankind prosperity, comfort and security. However, the critical infrastructures of future smart cities are expected to be large complex critical infrastructures (LCCIs) that need to be autonomous or self-adaptive to be able to survive in critical unpredictable situations. This chapter presents a new approach based on self-organizing multi-agent systems (So-MAS) for modeling and engineering future self-adaptive LCCIs. So-MAS are MAS that have the capability to dynamically and autonomously reorganize themselves to adapt the dynamic changes of work environment. Further, the proposed approach adopts a novel MAS organizational model (called as NOSHAPE) provided in [1, 2] designed to enable large-scale MAS to adaptively self-organize. Based on a simulation environment, a performance evaluation has been conducted that shows how the proposed approach is able to deal with the dynamic unanticipated work environment behaviors. Up to 47% of performance improvement has been achieved with the proposed approach compared to conventional organizational techniques in MAS (i.e. federation). Further future research is still required to address important issues of future smart cities and their associated LCCIs such as security, and resiliency.