Aarestrup var københavner, født 4. december 1800 i Store Kongensgade. Faderen, Jørgen Fog Aarestrup, der var toldkontrollør ved Østerport, skal have været et festmenneske og en bonvivant. Moderen, Sophie Charlotte Aagaard, var datter af te- og porcelænshandler Rasmus Aagaard; i hans ejendom fik ægteparret Aarestrup tildelt en lejlighed. Til Chr. Petersen skriver Aarestrup 11.4.1844: "Du erindrer vel af Historien, at min Bedstefader var Urtekræmmer eller dog idetmindste Theehandler, og at mine Drengeaar tildeels have været paavirkede af Urtebodens sødmende, kryderagtige fidtede Athmosphære?" I det livfulde digt "Kjøbenhavnske Minder" (SS IV, 38. If. Oluf Friis skrevet 1838). beretter han om sine tidlige indtryk fra hovedstaden, sine legepladser og tilholdssteder, bl.a. den halvtopførte Marmorkirke, der først blev fuldført 1894: