In this paper we connect Calderón and Zygmund’s notion of Lp-differentiability (Calderón and Zygmund, Proc Natl Acad Sci USA 46:1385–1389, 1960) with some recent characterizations of Sobolev spaces via the asymptotics of non-local functionals due to Bourgain, Brezis, and Mironescu (Optimal Control and Partial Differential Equations, pp. 439–455, 2001). We show how the results of the former can be generalized to the setting of the latter, while the latter results can be strengthened in the spirit of the former. As a consequence of these results we give several new characterizations of Sobolev spaces, a novel condition for whether a function of bounded variation is in the Sobolev space W1,1, and complete the proof of a characterization of the Sobolev spaces recently claimed in (Leoni and Spector, J Funct Anal 261:2926–2958, 2011; Leoni and Spector, J Funct Anal 266:1106–1114, 2014).