“You can judge a man by his shoes” is an old fashion adage. “A fashion authority says you cannot always tell a man by his clothes, but you can invariably judge a gentleman by his shoes” was cited in print in 1891.
 
“Judge a Man by his Shoes” was cited in a popular shoe advertisement in 1899 and “Know a gentleman by the shoes he wears” was in a 1903 shoe advertisement. “You know it’s an old saying that a lady is told by her gloves and a gentleman by his shoes” was cited in print in 1905. “The age old saying, ‘You can judge a man by his shoes’ still holds good” was cited in 2014.
 
 
24 October 1891, Evening Bulletin (San Francisco, CA), “Fashion Notes,” supplement, pg. 2, col. 5:
A fashion authority says you cannot always tell a man by his clothes, but you can invariably judge a gentleman by his shoes.
 
28 November 1899, Idaho Statesman (Boise, ID), pg. 4, col. 5 ad:
Judge a Man by his Shoes
Handsome, perfect fitting shoes betoken the active, energetic, successful man, who knows the value of tidy dress and its suggestion of prosperity.
(Humanic shoes at Logan & Walker.—ed.)
 
Old Fulton NY Post Cards
19 April 1903, Philadelphia (PA) Inquirer, pg. 14, col. 1 ad:
$5 Men’s Oxfords
“Know a gentleman by the shoes he wears,”—doesn’t cost much either.
(Steigerwalt, Shoemaker.—ed.)
 
15 January 1905, Trenton (NJ) Sunday Advertiser, pg. 6, col. 7 ad:
An Old Saying
You know it’s an old saying that a lady is told by her gloves and a gentleman by his shoes.
(Gallavan.—ed.)
 
2 January 1910, Denver (CO) Post, pg. 2, col. 6:
One Way.
“You can always tell a gentleman by his shoes.”
“Yes, all’s swell that ends swell.”—Harvard Lampoon.
 
Chronicling America
9 June 1917, The Daily Gate City and Constitution-Demcorat (Keokuk, IA), pg. 8, col. 1 ad:
JUDGE A MAN BY HIS SHOES
Now that these warm Spring days have coaxed you to dress Summer, it is imperative that your oxfords—the essential footwear for Summer—look the part of the position you occupy in walks of life.
(Baur-Mullarky Co.—ed.)
 
22 February 1926, Le Mars (IA) Globe-Post, “Hints for the Household” by Betty Webster, pg. 6, col. 1:
Shoes
Shoes are a most important part of a person’s attire. I have heard it said many times that “one can always tell a gentleman by his shoes.”
 
Google Books
100 Best Album Covers:
The Stories Behind the Sleeves
By Storm Thorgerson, Aubrey Powell, et al.
London: DK Pub.
1999
Pg. 1988:
This arresting image for Joe Jackson’s debut album just goes to show that the old adage—you can tell a man by his shoes—was still appropriate then, if not today.
   
MensXP
9 Celebrity Fashion Quotes Every Guy Should Live By
By Nikita Mukherjee,
Wednesday, 10 Sep 2014
(...)
9) The age old saying, ‘You can judge a man by his shoes’ still holds good. Shoes are not just mere accessories but something inherently vital to a man’s wardrobe.  Therefore, it’s important to invest in quality pair of shoes. They have the potential to make or break your look.