Sullivan had worked for the FBI since 1941, after graduating from law school in the late thirties. By the early 1950's, Sullivan had joined the FBI's Domestic Intelligence division, whose responsibilities included keeping an eye on the KKK and other violent organizations. After heading bureau offices in Houston and Alaska, Sullivan was promoted in 1963 to the position of Major Case Inspector. It was a job that required him to be almost continuously on the road, but well suited to Sullivan who was at the time a widower with grown children. Sullivan quickly developed a reputation for thoroughness and efficiency.
In June, 1964, Sullivan was visiting FBI offices in New Orleans and Memphis to determine whether the agency was prepared to deal with an expected increase in Klan violence. Sullivan was still in Memphis on that fact-finding journey when he received word that the FBI had been authorized to investigate the disappearance the day before of three civil rights workers near Philadelphia, Mississippi. Sullivan flew to Meridian which would become his home for the next nine months of the investigation.
It soon became apparant to Sullivan that the Johnson Administration was determined to spare no costs to track down the killers. Sullivan reported that "the pressure from Washington for some solution..was really intense." Within weeks after his arrival in Mississippi, Sullivan was visited first by FBI Assistant Director Al Rosen, then by FBI Director J. Edgar Hoover, who met Sullivan in Jackson. Sullivan's investigation was even assisted by the military, which sent busloads of sailors from the Meridain Naval Station to aid in the search for bodies in the snake and bug infested woods and swamps of east central Mississippi.
Sullivan reached the conclusion that he "would ultimately solve this case by an investigation rather than a search." The investigation was not made easy by tight-lipped Philadelphians. Sullivan said "They [the Klan] owned the place. In spirit everyone belonged to the Klan." Local residents would often delight in sending Sullivan's agents on wild goose chases. Eventually informants were developed that led to the uncovering of the central facts of the case. All the key informants were members of the Lauderdale County (Meridian) klavern, not the Neshoba County (Philadelphia) klavern, causing Sullivan to observe, "If the Neshoba klavern carried out the murders on their own, they would have almost certainly gotten away with it."
Sullivan undoubtedly derived great satisfaction from his success in the case. He repeatedly found himself disgusted with the racial attitudes of local law enforcement personel. When a local policeman expressed indifference to the plight of blacks at a local community center who were were being intimidated by gangs of white thugs, Sullivan grabbed the local lawman by his collar and said "You are a disgrace to your uniform."