Observations show that galaxies and their interstellar media are pervaded by strong magnetic fields with energies in the diffuse component being at least comparable to the thermal and even as large or larger than the turbulent energy. Such strong magnetic fields prevent the formation of stars because patches of the interstellar medium are magnetically subcritical. Here we present the results from global numerical simulations of strongly magnetised and self-gravitating galactic discs, which show that the buoyancy of the magnetic field due to the Parker instability leads at first to the formation of giant filamentary regions. These filamentary structures become gravitationally unstable and fragment into $sim10^5 M_{odot}$ clouds that attract kpc long, coherent filamentary flows that build them into GMCs. Our results thus provide a solution to the long-standing problem of how the transition from sub- to supercritical regions in the interstellar medium proceeds.