We study in this paper connection removal algorithms for multimedia CDMA wireless networks. In our study, users can have different data rates as well as different quality of service (QoS) requirements characterized by bit energy-to-interference ratios. In the distributed power control algorithm, connection removal mechanism is invoked if, after a pre-specified number of iterations of power control, QoS requirements are not satisfied. We prove in this paper that, if the transmitter power levels are not reset after a connection is removed, then a feasible power set can be found faster and the power levels employed are smaller. Performances of some connection removal criteria for multimedia CDMA wireless networks are also studied. Three connection removal criteria, i.e., smallest CIR, smallest normalized CIR and largest CIR requirement, are evaluated.