The Tera Electronvolt Superconducting Linear Accelerator TESLA is the only linear electron-positron collider project based on superconductor technology for particle acceleration. In the first stage with 500 GeV center-of-mass energy an accelerating field of 23.4 MV/m is needed in the superconducting niobium cavities which are operated at a temperature of 2 K and a quality factor Q0 of 10 to the 10. This performance has been reliably achieved in the cavities of the TESLA Test Facility (TTF) accelerator. The upgrade of TESLA to 800 GeV requires accelerating gradients of 35 MV/m. Using an improved cavity treatment by electrolytic polishing it has been possible to raise the gradient to 35 - 43 MV/m in single cell resonators. Here we report on the successful transfer of the electropolishing technique to multi-cell cavities. Presently four nine-cell cavities have achieved 35 MV/m, and a fifth cavity could be excited to 39 MV/m. In two high-power tests it could be verified that EP-cavities preserve their excellent performance after welding into the helium cryostat and assembly of the high-power coupler. One cavity has been operated for 1100 hours at the TESLA-800 gradient of 35 MV/m and 57 hours at 36 MV/m without loss in performance.