Patrick was born to an Italian immigrant and mason father and a social worker mother. He worked his way through college, spending his summers mixing cement and hauling bricks for his family's masonry business. Patrick attended Catholic University of America in Washington, D.C., where he played soccer at and graduated summa cum laude in 1990. The next year, Patrick attended Boston College's Thomas P. O'Neill Jr. Fellowship in American Government Program. Patrick came out to his family shortly after college, and they have been very supportive of him and his political endeavors ever since.

In 1993 Patrick was elected to the Massachusetts state house (35th Middlesex District) at the age of 25. He had an excellent voting record and fought for lower taxes, fiscal discipline, improved public schools, better public safety, and welfare reform. Patrick was a staunch supporter of the landmark 1993 Education Reform Act that required students pass standardized graduation tests (MCAS). He was also an advocate for gay and lesbian issues, effecting strict anti-hate crimes legislation and increased AIDS awareness funding.

Patrick was awarded the John F. Kennedy Library's Fenn Award for politicians 35 years of age and younger on November 10, 1998. In 1998, Patrick was elected mayor of the city of Melrose, Massachusetts with 85% of the vote. The residents elected him to a second term with over 80% of the vote. During his tenure as mayor, Patrick created a "civility initiative" which encouraged residents to show each other respect and courtesy. This project earned him the City Livability Award at the U.S. Mayor's Association 2000 City Livability Awards. He also led the way for the city building its first new public schools in over 30 years.

On January 1, 2003, Patrick succeeded Rich Tafel as the leader of the Log Cabin Republicans. Since accepting the position, Patrick has faced sharp criticism from both the left and the right. Minister Fred Phelps called him a "faggot... worthy of the death penalty." while a Democrat in Los Angeles dubbed him "just another self-hating faggot" in an e-mail and wrote, "You and people like you are the worst enemies of the gay community."

Patrick often writes op-ed pieces for Massachusetts newspapers. He praised the Massachusetts Supreme Judicial Court's 2003 decision in the case of Goodridge et al. v. Department of Public Health as a conservative ruling supporting stable families, relationships, and society, limited government, individual liberty, and religious freedom. Patrick has supported gay rights in the conservative tradition of Massachusetts Republican Governors William Weld and Paul Cellucci.