We consider the long-standing problem of obtaining the 3-point functions of Toda CFT. Our main tools are topological strings and the AGT-W relation between gauge theories and 2D CFTs. In arXiv:1310.3841 we computed the partition function of 5D $T_N$ theories on $S^4 \times S^1$ and suggested that they should be interpreted as the three-point structure constants of q-deformed Toda. In this paper, we provide the exact AGT-W dictionary for this relation and rewrite the 5D $T_N$ partition function in a form that makes taking the 4D limit possible. Thus, we obtain a prescription for the computation of the partition function of the 4D $T_N$ theories on $S^4$, or equivalently the undeformed 3-point Toda structure constants. Our formula, has the correct symmetry properties, the zeros that it should and, for $N=2$, gives the known answer for Liouville CFT.