Resonant soft x-ray diffraction (RSXD) with femtosecond (fs) time resolution is a powerful tool for disentangling the interplay between different degrees of freedom in strongly correlated electron materials. It allows addressing the coupling of particular degrees of freedom upon an external selective perturbation, e.g., by an optical or infrared laser pulse. Here, we report a time-resolved RSXD experiment from the prototypical correlated electron material magnetite using soft x-ray pulses from the free-electron laser FLASH in Hamburg. We observe ultrafast melting of the charge-orbital order leading to the formation of a transient phase, which has not been observed in equilibrium.