We apply the large-$N_c$ expansion to the time-reversal-invariance-violating (TV) nucleon-nucleon potential. The operator structures contributing to next-to-next-to-leading order in the large-$N_c$ counting are constructed. For the TV and parity-violating case we find a single operator structure at leading order. The TV but parity-conserving potential contains two leading-order terms, which however are suppressed by 1/$N_c$ compared to the parity-violating potential. Comparison with phenomenological potentials, including the chiral EFT potential in the TV parity-violating case, leads to large-$N_c$ scaling relations for TV meson-nucleon and nucleon-nucleon couplings.