Kelly entered politics in the 1840s, and was elected to the city's board of aldermen in 1853, supporting the measures of Tammany Hall.  The next year, however, he challenged their maverick congressman, Mike Walsh, and won by 18 votes, becoming the only Roman Catholic in Congress at the time. He served on the powerful House Ways and Means Committee, and was reelected in 1856.

In 1858, at the urging of Tammany leaders, Kelly ran and won election as city and county sheriff, resigning his congressional seat in the final months of his second term. The sheriff did not receive a salary, but was paid with a percentage of all fees the office collected. Kelly’s efficiency in the position brought him considerable wealth and the (some said ironic) nickname "Honest John."  He accumulated a fortune through his financial dealings as sheriff, businessman, and real estate investor, donating large sums to Catholic charities. 

In politics, Kelly had become increasingly dissatisfied with the way William "Boss" Tweed ran Tammany Hall, so in 1868 agreed to run for mayor on a Reform Democratic ticket against Tweed’s candidate, Oakey Hall. After losing, Kelly went on an extended tour of Europe.  He returned in the fall of 1871 when press revelations of "Tweed Ring" corruption and subsequent legal prosecutions were crippling Tammany Hall as a political force. Democratic reformers who helped topple Tweed and his cohorts did not want to see Tammany Hall destroyed, so they offered Kelly leadership of the organization. 

Kelly purged Tammany Hall of Tweed associates, and persuaded prominent, respectable Democrats, such as George McClellan, Horatio Seymour, and Abram Hewitt, to become members. Kelly consolidated power within the organization, becoming more of a boss than Tweed had ever been.  His control would never be complete, though, as he was forced to battle challengers, such as John Morrissey, founder of a competing Democratic political machine, Irving Hall. 

In 1876, Kelly won election as city comptroller (treasurer), and during his four-year term reduced municipal debt by $2 million. In 1879, having broken with Democratic governor Lucius Robinson, Kelly’s run for governor on the Tammany Democratic ticket against Robinson allowed Republican Alonzo Cornell to win the election. In the mid-1880s, Kelly suffered increasing ill health and transferred much of the Tammany leadership duties to Richard Croker, who became the new boss upon Kelly’s death in 1886.

In this cartoon, the source of Tammany Hall's power is a gin mill, and Kelly's seat of authority is the barrel containing the gin, reflecting the perspective of good-government reformers that Tammany Hall constituents were ignorant, besotted immigrants (Irish Catholics, mainly) and workingmen.  The label "Bourbon" (on the board upon which Kelly's feet rest) reinforces here the negative image of urban Democrats, but is also a nickname for conservative Southerners, the party's other power base.  Kelly's hypocrisy concerning the issue of alcohol prohibition is emphasized by the placard reading "This machine is run on Democratic temperance principles."