Recent theoretical studies indicate that reactive organic iodocarbons such as CH2I2 would be extremely effective agents for tropospheric Arctic ozone depletion and that iodine compounds added to a Br2/BrCl mixture have a significantly greater ozone (and mercury) depletion effect than additional Br2 and BrCl molecules. Here we report the first observations of CH2I2, CH2IBr, and CH2ICl in Arctic air, as well as other reactive halocarbons including CHBr3, during spring at Kuujjuarapik, Hudson Bay. The organoiodine compounds were present atthe highest levels yet reported in air. The occurrence of the halocarbons was associated with northwesterly winds from the frozen bay, and, in the case of CHBr3, was anticorrelated with ozone and total gaseous mercury (TGM), suggesting a link between inorganic and organic halogens. The absence of local leads coupled with the extremely short atmospheric lifetime of CH2I2 indicates that production occurred in the surface of the sea-ice/overlying snowpack over the bay. We propose an abiotic mechanism for the production of polyhalogenated iodo- and bromocarbons, via reaction of HOI and/or HOBr with organic material on the quasi-liquid layer above sea-ice/snowpack, and report laboratory data to support this mechanism. CH2I2, CH2IBr, and other organic iodine compounds may therefore be a ubiquitous component of air above sea ice where they will increase the efficiency of bromine-initiated ozone and mercury depletion.