We study the asymptotic behavior for large N of the disconnection time TN of a simple random walk on the discrete cylinder (ℤ/Nℤ)d×ℤ, when d≥2. We explore its connection with the model of random interlacements on ℤd+1 recently introduced in [Ann. Math., in press], and specifically with the percolative properties of the vacant set left by random interlacements. As an application we show that in the large N limit the tail of TN/N2d is dominated by the tail of the first time when the supremum over the space variable of the Brownian local times reaches a certain critical value. As a by-product, we prove the tightness of the laws of TN/N2d, when d≥2.