We study non-perturbative aspects of the large N duality between Chern-Simons theory and topological strings, and we find a rich structure of large N phase transitions in the complex plane of the 't Hooft parameter. These transitions are due to large N instanton effects, and they can be regarded as a deformation of the Stokes phenomenon. Moreover, we show that, for generic values of the 't Hooft coupling, instanton effects are not exponentially suppressed at large N and they correct the genus expansion. This phenomenon was first discovered in the context of matrix models, and we interpret it as a generalization of the oscillatory asymptotics along anti-Stokes lines. In the string dual, the instanton effects can be interpreted as corrections to the saddle string geometry due to discretized neighboring geometries. As a mathematical application, we obtain the 1/N asymptotics of the partition function of Chern-Simons theory on L(2,1), and we test it numerically to high precision in order to exhibit the importance of instanton effects.