Stroll has referred to “leisurely walking” since at least 1680, but in the beginning of the 1600s, the word wasn’t quite so innocent and carefree.
The Oxford English Dictionary (OED) first attests stroll in Thomas Dekker’s 1603 The Wonderful Year, a pamphlet which documented the death of Queen Elizabeth I, the accession of James I in her place, and the plague that claimed 30,000 Londoners that year. For Dekker, stroll meant to “roam” or “wander” like a vagrant: “He would…strowle (thats to say trauell [travel]) with some notorious wicked floundring companie abroade.”
English appears to have borrowed, via soldiers, stroll from a German dialectical variant of the Swiss German strolchen, “to stroll” or “loaf,” formed from the noun Strolch, a prowling “vagabond.” (Today, the word has the sense of a “hoodlum” or “rascal.”) According to the Barnhart Dictionary of Etymology, Strolch could also mean “fortuneteller” and thus perhaps came from the Italian astrologo, “astrologer,” who, apparently, practiced their craft (or cons) peripatetically.
In the 16th century, stroll went on to describe strolling players, poor, itinerant actors who wandered the countryside giving performances. They were also called strollers (1608), which weren’t pushing babies in American English until 1920, as recorded in a Sears, Roebuck and Co. catalog that year. The OED first cites the derived noun, a stroll, in Jane Austen’s 1814 Mansfield Park, “when the evening stroll was over,” showing just how far the word stroll had strolled.