MT first performed material from his Quaker City letters before an audience in Washington, DC, in early January 1868. When he went back to California that spring to get permission from the Alta Californian to use the letters in the book he was making for Bliss, he decided to give another series of lectures through eight of the cities and towns where he'd given his first lecture tour back in 1866, before leaving the frontier for the East and the trip to the Old World. The talk he gave was called "Pilgrim Life, Being a Sketch of His Notorious Voyage to Europe, Palestine, &c." Although there were objections to the irreverence of his depiction of the Holy Land in the pulpit and the press, audiences packed theatres in San Francisco, Sacramento, Virginia City (Nevada) and elsewhere to hear him. Based on that success, MT decided before leaving the west coast that he wanted to use the lecture as the basis for a full-scale lyceum circuit tour, though he knew that what pleased westerners might not work with more refined listeners east of the Mississippi.

For his first eastern lecture tour he registered with James Redpath's Boston Lyceum Bureau, a booking agency used by many of the period's most popular speakers. In October he revised "Pilgrim Life" as the lecture titled "The American Vandal Abroad" -- "That is to say," he wrote Mary Fairbanks, "I 'smouched' a lecture out of my book." He arranged to begin the tour under Mrs. Fairbanks' eye in Cleveland, on 17 November 1868; after speaking in over forty places, mainly in mid-Atlantic and middle-western states, he finished in early March, 1869. He spoke mainly in smaller cities, often just large towns, for a fixed fee -- "$100 a pop," as he wrote his mother.

While a few reviewers were critical, mainly because a humorous lecturer was still an anomaly on the lyceum circuit, most had nothing but praise for his performance, and his talks were popular. Many, it seems, sold out the house. As MT gained confidence along the way, he came to see the tour as a chance to promote his forthcoming book. From Chicago, on 7 January 1869, he wrote the American Publishing Company to ask: "Why don't you issue prospectuses and startling advertisements now while I am stirring the bowels of these communities? I have big houses -- and more invitations to lecture than I can fill."