Summary: The diversity of networked systems with fractal structures suggests that knowing the underlying mechanism that generates the fractality is necessary for building a model of the development of complex networks. In the present paper, we propose a growth model of a network generated by a random walk and show that the evolving graph forms a fractal structure with various properties including the scale-free property, if the graph which provides a space where a random walk occurs by itself is formed by the random walk. The proposed model is regulated by two parameters \(p_{\mathrm{v}}\) and \(p_{\mathrm{e}} \), which define the probability of either a roundabout path via a new vertex or a shortcut being formed by the random walk, respectively. The power-law exponent \(\gamma\) describing the vertex degree distribution is determined by the ratio \(p_{\mathrm{e}}/p_{\mathrm{v}}\) and is related to an internal factor \(F_{\mathrm{I}}\) via the relation \(\gamma = 1/F_{\mathrm{I}} + 1\), where \(F_{\mathrm{I}}\) is a parameter that describes the local structure generated by the random walk. A sufficiently small \(p_{\mathrm{v}}\) provides the small-world property to the model network. The small-world property is usually considered to be incompatible with the fractal scaling property \(\langle M_{\mathrm{c}}\rangle \sim l_{\mathrm{c}}^{d_{\mathrm{c}}}\), where \(\langle M_{\mathrm{c}}\rangle\) is the average number of vertices which can be reached from a randomly chosen vertex in at most \(l_{\mathrm{c}}\) steps. However, we demonstrate that fractality can be reconciled with the small-world property by introducing a size-dependent fractal cluster dimension \(d_{\mathrm{c}} \).