In this paper we explain why future probe storage systems will use patterned media. As a model system, magnetic patterned media will be discussed, even though their data density is limited to about $7Tbit/in^2$. The first results on magnetic probe storage on patterned media are presented, and the problem of switching field distribution is discussed in detail. Finally we will present the first steps into two-dimensional coding for patterned media.