This paper proposes a novel stochastic Fault Detection (FD) approach for the monitoring of Large-Scale Systems (LSSs) in a Plug-and-Play (PnP) scenario. The proposed architecture considers stochastic bounds on the measurement noises and modeling uncertainties, providing probabilistic time-varying FD thresholds with guaranteed false alarms probability levels. The monitored LSS consists of several interconnected subsystems and the designed FD architecture is able to manage plugging-in of novel subsystems and un-plugging of existing ones. Moreover, the proposed PnP approach can perform the unplugging of faulty subsystems in order to avoid the propagation of faults in the interconnected LSS. Analogously, once the issue has been solved, the disconnected subsystem can be re-plugged-in. The reconfiguration processes involve only local operations of neighboring subsystems, thus allowing a scalable architecture. A consensus approach is used for the estimation of variables shared among more than one subsystem; a method is proposed to define the time-varying consensus weights in order to allow PnP operations and to minimize at each step the variance of the uncertainty of the FD thresholds. Simulation results on a Power Network application show the effectiveness of the proposed approach.