Real-time functional magnetic resonance imaging (rtfMRI) enables classification of brain activity during data collection thus making inference results accessible to both the subject and experimenter during the experiment. The major challenge of rtfMRI is the potential loss of inference accuracy due to the resource limitations that rtfMRI imposes. For example, many widely-used analysis methods in off-line neuroimaging are too time-consuming for rtfMRI. We develop an online, real-time, conjugate gradient (rtCG) algorithm that learns to classify brain states as data is being collected. The algorithm is closely connected to partial least squares (PLS), a popular off-line analysis method. We give a theoretical comparison with PLS and show that the algorithm generates identical results to PLS for appropriate initial conditions. However, in practice using an alternative initial condition yields faster convergence. Experimental results show that the online rtCG classifier: is fast (training time < 0.5s), is accurate (prediction accuracy ≈ 90%), can adapt to a varying stimulus, and yields better classification performance than standard PLS applied to a sliding window of recent data.