In this paper, first we introduce the notion of a twisted Rota-Baxter operator on a 3-Lie algebra $g$ with a representation on $V$. We show that a twisted Rota-Baxter operator induces a 3-Lie algebra structure on $V$, which represents on $g$. By this fact, we define the cohomology of a twisted Rota-Baxter operator and study infinitesimal deformations of a twisted Rota-Baxter operator using the second cohomology group. Then we introduce the notion of an NS-3-Lie algebra, which produces a 3-Lie algebra with a representation on itself. We show that a twisted Rota-Baxter operator induces an NS-3-Lie algebra naturally. Thus NS-3-Lie algebras can be viewed as the underlying algebraic structures of twisted Rota-Baxter operators on 3-Lie algebras. Finally we show that a Nijenhuis operator on a 3-Lie algebra gives rise to a representation of the deformed 3-Lie algebra and a 2-cocycle. Consequently, the identity map will be a twisted Rota-Baxter operator on the deformed 3-Lie algebra. We also introduce the notion of a Reynolds operator on a 3-Lie algebra, which can serve as a special case of twisted Rota-Baxter operators on 3-Lie algebras.