The code capacity threshold for error correction using qubits which exhibit asymmetric or biased noise channels is known to be much higher than with qubits without such structured noise.However, it is unclear how much this improvement persists when realistic circuit level noise is taken into account. This is because implementations of gates which do not commute with the dominant error un-bias the noise channel. In particular, a native bias-preserving controlled-NOT (CX) gate, which is an essential ingredient of stabilizer codes, is not possible in strictly two-level systems. Here we overcome the challenge of implementing a bias-preserving CX gate by using stabilized cat qubits in driven nonlinear oscillators. The physical noise channel of this qubit is biased towards phase-flips, which increase linearly with the size of the cat, while bit-flips are exponentially suppressed with cat size. Remarkably, the error channel of this native CX gate between two such cat qubits is also dominated by phase-flips, while bit-flips remain exponentially suppressed. This CX gate relies on the topological phase that arises from the rotation of the cat qubit in phase space. The availability of bias-preserving CX gates opens a path towards fault-tolerant codes tailored to biased-noise cat qubits with high threshold and low overhead. As an example, we analyze a scheme for concatenated error correction using cat qubits. We find that the availability of CX gates with moderately sized cat qubits, having mean photon number <10, improves a rigorous lower bound on the fault-tolerance threshold by a factor of two and decreases the overhead in logical Clifford operations by a factor of 5. We expect these estimates to improve significantly with further optimization and with direct use of other codes such as topological codes tailored to biased noise.[/expand]