We introduce a model of random interlacements made of a countable collection of doubly infinite paths on ℤd, d≥3. A nonnegative parameter u measures how many trajectories enter the picture. This model describes in the large N limit the microscopic structure in the bulk, which arises when considering the disconnection time of a discrete cylinder (ℤ/Nℤ)d−1×ℤ by simple random walk, or the set of points visited by simple random walk on the discrete torus (ℤ/Nℤ)d at times of order uNd. In particular we study the percolative properties of the vacant set left by the interlacement at level u, which is an infinite connected translation invariant random subset of ℤd. We introduce a critical value u∗ such that the vacant set percolates for uu∗. Our main results show that u∗ is finite when d≥3 and strictly positive when d≥7.