Within a year, he was commanding an Active Service Unit of the IRA in South Derry, where his leadership skills earned him the nickname of "The Boy General". The most publicised actions of his unit included the destruction of bridges and the burning of Magherafelt courthouse.
He was arrested in Glencree, Co. Wicklow, in 1957 and sentenced to six months in Mountjoy Prison. On his release, he was immediately interned in the Curragh prison camp for two years.
He spent his time in prison studying. He was particulary inspired by his studies of the Vietnamese struggle. He became a member of the escape committee which engineered the successful escapes of Ruari O'Bradaigh and Daithi O'Connell, among others. Costello would later refer to this time as his "university days".
After his release, Costello worked to rebuild the Republican Movement, beginning by building a local base of support in Co. Wicklow as Sinn Féin's local organiser. He helped found a strong Tenants Association in Bray, and also became involved with the Credit Union movement and various farmers' organisations. During this period, he found time to marry a Tipperary woman, Maeliosa, who also became active in the Republican Movement. Costello stood for election to the Bray Urban District Council in 1967 and was successful.
During the split of the Republican Movement into Official and Provisional movements in 1969, Costello remained with the Officials, serving as Vice-President of Official Sinn Féin and as a Staff Officer in the Official IRA.
As the Officials began their slide into reformist politics, Costello's opposition caused him to be dismissed from the OIRA and suspended from OSF. He was dismissed from OSF in 1974 after the OSF leadership undemocratically blocked his supporters from attending the party convention.
At a meeting in the Lucan Spa, a hotel near Dublin, on 10 December 1974, the Irish Republican Socialist Party was formed by republicans, socialists, and trade unionists with Costello as the Chairperson.
At a private meeting later the same day, the Irish National Liberation Army was formed with Costello as the Chief of Staff, although its existence was to be kept secret for a time.
Within days of its founding, the fledgling Irish Republican Socialist Movement was to begin a baptism of fire at the hands of the OIRA. Members of the IRSM would be attacked and even killed. Before a truce was reached, three members of the young movement were dead.
Despite the truce, Costello was gunned down by a member of the OIRA in Dublin on 5 October 1977.
At the time of his death, he was a member of the following bodies: Wicklow County Council, County Wicklow Committee of Agriculture, General Council of Committees of Agriculture, Eastern Regional Development Organisation, National Museum Development Committee, Bray Urban District Council, Bray Branch of the Irish Transport and General Workers Union, Bray and District Trade Unions Council (of which he was president 1976-77), and the Cualann Historical Society, as well as still holding the positions of Chairperson of the IRSP and Chief of Staff of the INLA.
At his funeral, James Connolly's daughter Nora said "he was the only one who truly understood what James Connolly meant when he spoke of his vision of the freedom of the Irish people."