A Rota-Baxter Leibniz algebra is a Leibniz algebra $(\mathfrak{g},[~,~]_{\mathfrak{g}})$ equipped with a Rota-Baxter operator $T : \mathfrak{g} \rightarrow \mathfrak{g}$. We define representation and dual representation of Rota-Baxter Leibniz algebras. Next, we define a cohomology theory of Rota-Baxter Leibniz algebras. We also study the infinitesimal and formal deformation theory of Rota-Baxter Leibniz algebras and show that our cohomology is deformation cohomology. Moreover, We define an abelian extension of Rota-Baxter Leibniz algebras and show that equivalence classes of such extensions are related to the cohomology groups.