Brady was born in Philadelphia, the son of Enez (née Caterini) and Robert G. Brady, a police officer. His father was of Irish descent, and his maternal grandparents were immigrants from Italy. His mother Enez was also a Democratic committee member. He graduated from St. Thomas More High School and Martin Technical School but did not attend college, instead going to work as a carpenter and member of Carpenters Local 8. He became a part of the leadership of the union and remains a member of several unions.