Dynamic changes in service environment will affect fault diagnosis algorithm. In order to reduce the impact, challenges of fault diagnosis in dynamic environment are analyzed in this paper. Multi-layer management model is presented to model the service system, Bipartite Bayesian network is chosen to model the dependency relationship and binary symmetric channel is chosen to model noises. To deal with the dynamic fault set caused by fault recovery mechanism, prior fault probability is modified based on fault persistent time statistic; To deal with the dynamic model, expected model is built based on the time of observing symptoms and original models in current window. Simulation results show that this fault diagnosis algorithm is efficient in dynamic Internet service environment.