Anomalies of global symmetries are important tools for understanding the dynamics of quantum systems. We investigate anomalies of non-invertible symmetries in 3+1d using 4+1d bulk topological quantum field theories given by Abelian two-form gauge theories, with a 0-form permutation symmetry. Gauging the 0-form symmetry gives the 4+1d “inflow” symmetry topological field theory for the non-invertible symmetry. We find a two levels of anomalies: (1) the bulk may fail to have an appropriate set of loop excitations which can condense to trivialize the boundary dynamics, and (2) the “Frobenius-Schur indicator” of the non-invertible symmetry (generalizing the Frobenius-Schur indicator of 1+1d fusion categories) may be incompatible with trivial boundary dynamics. As a consequence we derive conditions for non-invertible symmetries in 3+1d to be compatible with symmetric gapped phases, and invertible gapped phases. Along the way, we see that the defects characterizing Z₄ ordinary symmetry host worldvolume theories with time-reversal symmetry T obeying the algebra T² = C or T² = (−1)^FC, with C a unitary charge conjugation symmetry. We classify the anomalies of this symmetry algebra in 2+1d and further use these ideas to construct 2+1d topological orders with non-invertible time-reversal symmetry that permutes anyons. As a concrete realization of our general discussion, we construct new lattice Hamiltonian models in 3+1d with non-invertible symmetry, and constrain their dynamics.