We generalize the scale-free network model of Barabàsi and Albert [Science 286, 509 (1999)] by proposing a class of stochastic models for scale-free interdependent networks in which interdependent nodes are not randomly connected but rather are connected via preferential attachment (PA). Each network grows through the continuous addition of new nodes, and new nodes in each network attach preferentially and simultaneously to (a) well-connected nodes within the same network and (b) well-connected nodes in other networks. We present analytic solutions for the power-law exponents as functions of the number of links both between networks and within networks. We show that a cross-clustering coefficient vs. size of network $N$ follows a power law. We illustrate the models using selected examples from the Internet and finance.