Green’s Dictionary of Slang

a notice of dismissal.

1861		E.S. Ellis Life of Col. David Crockett 170: He got his walking orders, and Taney was taken into his place. Why? Because he had agreed to do what Duane had refused.
1900		Dundee Courier 12 July 4/7: Li Hung Chang Receives Walking Orders [...] an Imperial decree ordering his immediate departure.
[1905		Marvel III:53 8: And I suppose the old man gave him orders to walk arter that, sir?].
1916		Dundee Courier 17 Jan. 3/5: The outside right got his walking orders.
1922		Post 26 Nov. 13/2: It was a great finish to a glorious game married only by one deliberate act that earned Howieson his walking orders.
1939		Eve.Teleg. (Dundee) 20 Mar. 8/1: Morrison [...] proceeded to tell the referee ‘something’ hence the walking orders.

1. (US) a notice of dismissal.

1834		D. Crockett Narrative of Life of D.C. (1934) 22: I didn’t know how soon I should be knocked into a cocked hat, and get my walking papers for another country.
1843		‘Madison Tensas’ Louisiana ‘Swamp Doctor’ (1850) 71: As my uncle remarked [...] when the department gave him his walking papers.
1850		N.Y. Herald 1 Feb. 1/2: Dr. Gardiner [...] has also received his ‘walking papers.’.
1862		Letters of Major Jack Downing 8 June in R.H. Thornton Amer. Gloss. (1912) II 930: He will think that you’ll be sure to give him his walking papers.
1871		Wash. Patriot 21 Apr. in Schele De Vere (1872) 647: It was said, yesterday, that a number of town officials, as well as many of the officers of the former District, had already received their walking-papers, but the announcement is premature.
1885		Atchison (KS) Globe 24 Apr. 3/4: Some fine day he gets his walking papers, and there is no appeal from the judgement.
1899		H. Garland Boy Life on the Prairie 287: ‘Here’s your “walking papers,”’ he said grimly.
1906		G. Fitzmaurice ‘Cupid and Cornelius’ in Irish Weekly Indep. 10 May (1970) 104: Come in, come in, girrul, till I give ye your walkin’ papers.
1916		Joyce Portrait of the Artist as a Young Man 21: You’ll get your walking papers in the morning when the doctor comes.
1932		L.E. Lawes Twenty Thousand Years in Sing Sing 27: We daily expected our walking papers.
1953		W. Brown Monkey On My Back (1954) 108: So Mamma Lin had given the Chinese their walking papers.
1965		(con. 1930s) R. Wright Lawd Today 128: ‘Doc fix it?’ ‘Sure! he ’phoned in when I was getting my walking papers.’.
1971		E.E. Landy Underground Dict. (1972).
1985		T. Wolff ‘Soldier’s Joy’ in Back in the World 117: ‘We’re all going to get another chance [...] Otherwise I’d take my walking papers and hat up’.

2. (also papers) an announcement that a relationship is over; divorce papers.

1825		S. Woodworth Forest Rose I iv: As for the bumpkin, her lover, he must take his walking papers.
c.1840		in N.E. Eliason Tarheel Talk (1956) 287: I am kicked . . . she said ‘I fear I do not love you’ . . . I had my papers.
1865		Leaves from Diary of Celebrated Burglar 158/1: Poll has had a quarrel with him [i.e. a live-in lover] and he is said to have got his walking papers — served him right, the dirty little varmint.
1900		H. Garland Eagle’s Heart 219: She wants to see you bad [...] I think she has given King his walking papers — and all on account of you.
1942		Pittsburgh Courier (PA) 25 July 21/1: [H]is ofay chick had given him his walkin’ papers.
1949		Wodehouse Mating Season 56: Shortly after Corky handed me my papers, I went to the pictures in Basingstoke.
1959		W. Brown Teen-Age Mafia 18: Stockow had made a pass at her and she’d given him his walking papers.
1968		N. Heard Howard Street 161: That was why she hadn’t given him his walking papers when he’d first broached the subject.
1974		J. Lahr Hot to Trot 233: Are you asking for your walking papers?
1986		H. Selby Jr Song of the Silent Snow (1988) 75: They start comin on with that, do it my way or else, bullshit an ya gotta givem their walkin papers.

3. (US prison) an official notice to inform a prisoner that they have finished their sentence.

1983		R. Klein Jailhouse Jargon and Street Sl. [unpub. ms.].
2000		(con. 1940s–60s) Décharné Straight from the Fridge Dad.