We prepared trirutile-type polycrystalline samples of CuTa2O6 by low-temperature decomposition of a Cu-Ta-oxalate precursor. Diffraction studies at room temperature identified a slight monoclinic distortion of the hitherto surmised tetragonal trirutile crystal structure. Detailed high-temperature X-ray and neutron powder diffraction investigations as well as Raman scattering spectroscopy revealed a structural phase transition at 503(3) K from the monoclinic structure to the tetragonal trirutile structure. GGA+U density functional calculations of the spin-exchange parameters as well as magnetic susceptibility and isothermal magnetization measurements reveal that CuTa2O6 is a new 1D Heisenberg magnet with predominant anti-ferromagnetic nearest-neighbor intrachain spin-exchange interaction of ∼50 K. Interchain exchange is a factor of ∼5 smaller. Heat capacity and low-temperature high-intensity neutron powder diffraction studies could not detect long-range order down to 0.45 K.