After graduating from Columbia, McCarthy became a Deputy United States Marshal in the Federal Witness Protection Program. In 1995, McCarthy led the successful prosecution of Sheikh Omar Abdel-Rahman and eleven others for planning and carrying out the 1993 World Trade Center bombing and the planning of a series of further attacks against New York City landmarks. McCarthy led the satellite office of the Southern District, in White Plains, New York, for five years, where he investigated the 1998 bombings of United States embassies in Kenya and Tanzania.