This work extends the near complete decomposability concept of Markov chains to SANs so that the inherent difficulty associated with solving the underlying MC can be forecasted and solution techniques based on this concept can be investigated. A straightforward approach to finding a nearly completely decomposable (NCD) partitioning of the MC underlying a SAN requires the computation of the nonzero elements of its global generator. This is not feasible for very large systems even in sparse matrix representation due to memory and execution time constraints. An efficient decompositional solution algorithm to this problem that is based on analyzing the NCD structure of each component of a given SAN is introduced. Numerical results show that the given algorithm performs much better than the straightforward approach.