In 1950, while a senior at Holy Cross, Costello ran for one of the 18th Suffolk district seats in the Massachusetts House of Representatives. The 18th Suffolk district consisted of Costello's home neighborhood of Jamaica Plain, as well as Forest Hills and Roslindale. During the final month of the primary race, he practiced football in the afternoon and campaigned at night. He finished second out of sixteen candidates in the Democratic primary, which secured him a spot on the general election ballot and, due to the 18th Suffolk being a strong Democratic district, was tantamount to election. During his first year in the legislature, Costello attended class during the day, worked at the state house during the afternoon, and studied at night. Costello remained in the House for ten years and for a time was a member of the House Ways and Means Committee. While a member of the House, Costello earned a law degree from the Suffolk University Law School.
In 1961, he was selected by the Massachusetts General Court to fill a vacancy on the Massachusetts Governor's Council caused by Edward J. Cronin's appointment as clerk of the Newton District Court. He was chosen over fellow representative Anthony Colonna 25 votes to 5 in the Senate and 125 to 99 in the House. Costello was elected to the Council in his own right in 1962 and reelected in 1964.
On May 18, 1964, Costello announced his candidacy for Lieutenant Governor. He was one of fourteen candidates going into the Democratic convention and won the party's endorsement on the fifth ballot by defeating Worcester attorney and Industrial Accident Board member Joseph E. McGuire 724 votes to 691 after five rounds of balloting. None of Costello's convention opponents chose to run in the primary and he won the nomination unopposed. In the general election, Costello was defeated by Republican Elliot Richardson 50% to 49%. In 1966, Costello was again a candidate for Lieutenant Governor. However, this time the convention endorsement was won by McGuire, who defeated Costello, John J. McGlynn, and John F. Dever Jr. after only two rounds balloting. Costello chose to drop out of the race after the convention.
Attempted comeback
In 1998, Costello ran for his old seat on the Governor's Council. He finished fifth in an eight candidate Democratic primary.
