Following second stage depletion compression, more than 100 deep onshore gas wells operated by PDO in the Sultanate of Oman started suffering from downhole halite deposition. Halite scale blocks part of production and reduces well capacity by 20-80% depending on well specific conditions. Fresh water bullheading treatments were introduced to periodically dissolve the halite scale but in many cases treatments were applied too late or are not effective in preventing permanent blockage. In those cases, a cleanout using a work string is required to restore wellbore access and production. Historically, coiled tubing was used to remove halite scale via milling and fresh water jetting. Recently, 1/4" and 3/8" capillary strings were successfully deployed to reduce the cleanout cost and the volume of water lost to formation. This paper describes the experience with fresh water bulheading and the novel use of capillary string to clean wells that suffer from halite scale.