We have performed a high sensitivity observation of the UFO/BAL quasar APM 08279+5255 at z=3.912 with NOEMA at 3.2mm, aimed at detecting fast moving molecular gas. We report the detection of blueshifted CO(4-3) with maximum velocity (v95%) of -1340km/s, with respect to the systemic peak emission, and a luminosity of L'=9.9x10^9^{mu}^-1^K.km/s/pc^2^, where {mu} is the lensing magnification factor. We discuss various scenarios for the nature of this emission and conclude that this is the first detection of fast molecular gas at redshift >3. We derived a mass flow rate of molecular gas in the range dM/dt=3-7.4x10^3^M_{sun}/yr and momentum boost (dP_OF/dt)/(dP_AGN_/dt)~2-6, which is therefore consistent with a momentum conserving flow. For the largest dP_OF_ the scaling is also consistent with an energy conserving flow with an efficiency of ~10-20%. The present data can hardly discriminate between the two expansion modes. The mass loading factor of the molecular outflow {eta}=(dM_OF_/dt)/SFR is >>1. We also detected a molecular emission line at a frequency of 94.83GHz corresponding to a rest-frame frequency of 465.8GHz; we tentatively identified this frequency with the cation molecule N_2_H^+^(5-4), which would be the first detection of this species at high redshift. We discuss the alternative possibility that this emission is due to a CO emission line from the, so far undetected, lens galaxy. Further observations of additional transitions of the same species with NOEMA can discriminate between the two scenarios.