Costello was born in Birmingham and after playing his youth football with Soho Villa he joined West Bromwich Albionin September 1904. Failing to make the grade he moved to Halesowen Town before moving to the south coast to join Southern League Southampton in the 1907 close season. He made his professional debut on 14 September 1907, scoring in a 2–0 victory at Luton Town. He initially played at inside right alongside Bert Hodgkinson on the outside and either Frank Jefferis, John Lewis or George Smith in the centre. Described as "a trifle slow, he was clever with the ball and had a habit of disconcerting the opposition by making for goal when he was expected to make a pass". In the 1907–08 season he scored nine goals from 28 league appearances. He also played in all six FA Cup matches as Saints reached the semi-finals, losing to Wolverhampton Wanderers who went on to take the cup in the final. In the round four replay against Everton at The Dell on 11 March 1908 he played his best game for the "Saints". In the first half he hooked a John Johnston cross past the Everton goalkeeper Billy Scott. With the score 2–1 to Southampton at half-time, the second half "belonged to Frank Costello". He was involved in most of Southampton's attacks and when John Bainbridge swung over a deep cross from the right it appeared to have been over hit and going out of play. Suddenly, "out of nowhere", Costello arrived and met the ball with his head, sending it back over the goalkeeper into the far corner of the net. According to Duncan Holley in "Match of the Millennium", "a contortionist would have had problems attaining a position... to reach the ball." The Saints won the match 3–2, but lost to Wolverhampton Wanderers in the semi-final with goals from former Southampton playersWally Radford and George Hedley. Injury kept him out of the team for the early part of the 1908–09 season; he had a run of five matches at inside left in November before being switched to centre forward as replacement for Arthur Hughes who had suffered a bad leg injury. Although Costello scored in his first match in his new role, he was not a success and in March 1909 he was transferred to West Ham United, with Jack Fostermoving in the opposite direction. He made twelve Southern League appearances for West Ham before moving on to Bolton Wanderers. He failed to make the first team at Bolton and after spells with Nelson and Merthyr Town he returned to Southampton, where he turned out occasionally for Salisbury City.
