The Modularity Theorem says every elliptic curve over $\mathbb{Q}$ can be gotten from the classic modular curve $X_0(N)$ by a rational map. Here $N$ is the conductor, easily calculable from a polynomial for the curve. Are the coefficients of the map calculable?

Unless this has changed lately, the proofs rely on some non-effective results. For example, Brian Conrad's comment at Can you get Siegel's theorem "for free" from modularity and Mazur's Eisenstein Ideal paper? points out that proofs of the modularity theorem (at least at that time) use the Shafarevich conjecture, which was proved by Faltings as a consequence of the once Mordell conjecture -- now Faltings's theorem.

At least up to Levin http://arxiv.org/abs/1109.6070 the Shafarevich conjecture is not (yet) effective. But I do not know how that conjecture is used for Modularity. See also Damian Rössler's comment at Effective proofs of Siegel's theorem using arithmetic geometry.

To clarify: effective proof is not the same thing as constructive proof. As Noam Elkies's and Qiaochu Yuan's answers say this theorem is effective because you can calculate the coefficients once you know the curve is modular, so the relevant searches will return results. A constructive proof would also require effectiveness at each step to show all the relevant searches indeed return results. That would be a further question.