We study the nature and the origin of the dust arch in the halo of the edge-on galaxy NGC 4631 detected by Neininger & Dumke (1999). We present CO observations made using the new On-The-Fly mapping mode with the FCRAO 14m telescope, and find no evidence for CO emission associated with the dust arch. Our examination of previously published HI data shows that if previous assumptions about the dust temperature and gas/dust ratio are correct, then there must be molecular gas associated with the arch, below our detection threshold. If this is true, then the molecular mass associated with the dust arch is between 1.5 x 10^8 M(sun)and 9.7 x 10^8 M(sun), and likely towards the low end of the range. A consequence of this is that the maximum allowed value for the CO-to-H_2 conversion factor is 6.5 times the Galactic value, but most likely closer to the Galactic value. The kinematics of the HI apparently associated with the dust arch reveal that the gas here is not part of an expanding shell or outflow, but is instead two separate features (a tidal arm and a plume of HI sticking out into the halo) which are seen projected together and appear as a shell. Thus there is no connection between the dust arch and the hot X-ray emitting gas that appears to surround the galaxy Wang et al. (2001).