How long does it take to entangle two distant qubits in a quantum circuit evolved by generic unitary dynamics? We show that if the time evolution is followed by measurements of all but two infinitely separated test qubits, then the entanglement between them can undergo a phase transition and become nonzero at a finite critical time t_{c}. The fidelity of teleporting a quantum state from an input qubit to an infinitely distant output qubit shows the same critical onset. Specifically, these finite-time transitions occur in short-range interacting two-dimensional random unitary circuits and in sufficiently long-range interacting one-dimensional circuits. The phase transition is understood by mapping the random continuous-time evolution to a finite-temperature thermal state of an effective spin Hamiltonian, where the inverse temperature equals the evolution time in the circuit. In this framework, the entanglement between two distant qubits at times t>t_{c} corresponds to the emergence of long-range ferromagnetic spin correlations below the critical temperature. We verify these predictions using numerical simulation of Clifford circuits and propose potential realizations in existing platforms for quantum simulation.