DNA replication initiation proteins (Reps) are subjected to degradation by cellular proteases. We investigated how the formation of nucleoprotein complex, involving Rep and a protease, affects Rep degradation. All known Escherichia coli AAA+ cytosolic proteases and the replication initiation protein TrfA of the broad-host-range plasmid RK2 were used. Our results revealed that DNA influences the degradation process and that the observed effects are opposite and protease specific. In the case of ClpXP and ClpYQ proteases, DNA abolishes proteolysis, while in the case of ClpAP and Lon proteases it stimulates the process. ClpX and ClpY cannot interact with DNA-bound TrfA, while the ClpAP and Lon activities are enhanced by the formation of nucleoprotein complexes involving both the protease and TrfA. Lon has to interact with TrfA before contacting DNA, or this interaction can occur with TrfA already bound to DNA. The TrfA degradation by Lon can be carried out only on DNA. The absence of Lon results with higher stability of TrfA in the cell.