Flynn made his Dublin debut when appearing as a second-half substitute in Dublin's first-round O'Byrne Cup victory over Wicklow on 5 January 2008 in Parnell Park. Flynn made his National Football League debut for Dublin against Westmeath and scored a goal in the process, helping guide his team to a first-round victory.
He made his Championship debut against Westmeath on Sunday 29th. On 18 September 2011, Flynn helped Dublin claim their first All-Ireland title in sixteen years, as they beat Kerry at Croke Park. He was awarded his first All Star Award for his performances for Dublin in the half forwards in 2011. Under Pat Gilroy's management term Paul Flynn became a regular in the Dublin half-forward line and was selected as Dublin's lone All Star in 2012. In 2013, he complained about a lack of intensity of the Dubs and he brought amazing fitness levels and intensity to the team. On 22 September 2013, Dublin won the All-Ireland Senior Football Championship with a big help from Paul Flynn in the half-forward line wearing number 10. He played twice for Ireland against Australia in the 2013 International Rules Series.