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 similar to 50 K. Interchain exchange is a factor of smaller. Heat capacity and low-temperature high-intensity neutron powder diffraction studies could not detect long-range order down to 0.45 K.