Recruiting an army dates back to earlier editions of D&D.
Dungeons & Dragons originated in tabletop wargaming, and players sometimes developed a series of battles as a campaign, the simulation of which extended to the conquest of real-world or fictional territory, the establishment of castles, and the hiring of troops. This concept transferred naturally into D&D.
In the original 1974 D&D rules, characters could hire men-at-arms and other forces, at a price. Clerics who reached a certain level could build a stronghold and acquire faithful followers who serve at no cost, while fighters could similarly acquire troops and establish themselves as a baron.
In AD&D 1st edition, a fighter who attains 9th level may establish a freehold, automatically attracting a body of men-at-arms, though he must still pay them a monthly fee. The cleric likewise can establish a religion stronghold.
You similarly see rules like this in the AD&D 2nd edition Player's Handbook, where the 9th level fighter attracts both low-level men-at-arms and an elite bodyguard ("bodyguard" in this case meaning a unit of troops, not just one individual). A table allows the fighter to roll to see what sort of units he might recruit. The cleric still gets to build a stronghold and can attract loyal followers.
D&D 3.0 removed the fighter and cleric's ability to acquire minions, but instead used the feat system to open this ability up to characters of all classes. The idea of Leadership modifiers is similar to the hireling rules in OD&D, where one's Charisma score affects the number of hirelings you can have and how loyal they will be, and the manner in which you treat your men can affect their loyalty.