We present a measure of the power spectrum on scales from 15 to 800 Mpc/h using the ROSAT-ESO Flux-Limited X-Ray(REFLEX) galaxy cluster catalogue. The REFLEX survey provides a sample of the 452 X-ray brightest southern clusters of galaxies with the nominal flux limit S=3.0 10^{-12}erg/s/cm2 for the ROSAT energy band (0.1-2.4)keV. Several tests are performed showing no significant incompletenesses of the REFLEX clusters with X-ray luminosities brighter than 10^{43}erg/s up to scales of about 800 Mpc/h. They also indicate that cosmic variance might be more important than previous studies suggest. We regard this as a warning not to draw general cosmological conclusions from cluster samples with a size smaller than REFLEX. Power spectra, P(k), of comoving cluster number densities are estimated for flux- and volume-limited subsamples. The most important result is the detection of a broad maximum within the comoving wavenumber range 0.022<k<0.030 h/Mpc. The data suggest an increase of the power spectral amplitude with X-ray luminosity. Compared to optically selected cluster samples the REFLEX P(k)is flatter for wavenumbers k<0.05 h/Mpc thus shifting the maximum of P(k) to larger scales. The smooth maximum is not consistent with the narrow peak detected at k=0.05 h/Mpc using the Abell/ACO richness $ge 0$ data. In the range 0.02<k<0.4 h/Mpc general agreement is found between the slope of the REFLEX P(k) and those obtained with optically selected galaxies. A semi-analytic description of the biased nonlinear power spectrum in redshift space gives the best agreement for low-density Cold Dark Matter models with or without a cosmological constant.