We report the observation of a new phenomenon of colossal magnetoresistance in a 40 nm wide GaAs quantum well in the presence of an external magnetic field applied parallel to the high-mobility 2D electron layer. In a strong magnetic field, the magnetoresistance is observed to increase by a factor of ∼300 from 0 to 45 T without the system undergoing any metal-insulator transition. We discuss how this colossal magnetoresistance effect cannot be attributed to the spin degree of freedom or localization physics, but most likely emanates from strong magneto-orbital coupling between the two-dimensional electron gas and the magnetic field. Our observation is consistent with a field-induced 2D-to-3D transition in the confined electronic system.