When an experimentalist measures a time series of qubits, the outcomes constitute a classical stochastic process. We show that projective measurement induces high complexity in these processes in two specific senses: They are inherently random (finite Shannon entropy rate) and they require infinite memory for optimal prediction (divergent statistical complexity). We identify nonorthogonality of the quantum states as the mechanism underlying the resulting complexities and examine the influence that measurement choice has on the randomness and structure of measured qubit processes. We introduce quantitative measures of this complexity and provide efficient algorithms for their estimation.