Nucl.Instrum.Meth.A552:372-398,2005 We describe the design, construction and performance of the upgraded DO muon system for Run II of the Fermilab Tevatron collider. Significant improvements have been made to the major subsystems of the DO muon detector: trigger scintillation counters, tracking detectors, and electronics. The Run II central muon detector has a new scintillation counter system inside the iron toroid and an improved scintillation counter system outside the iron toroid. In the forward region, new scintillation counter and tracking systems have been installed. Extensive shielding has been added in the forward region. A large fraction of the muon system electronics is also new.