Sullivan claimed Hoover's concerns about the American Communist Party were overemphasized when compared to violations of Federal civil rights laws in the segregrated south. This friction worsened as Sullivan made his opinions public. In 1971 Sullivan's FBI career ended abruptly after Hoover ordered the lock on his door changed and his nameplate removed.
Sullivan then became even more vocal about Hoover's controversial counterintelligence programs, collectively labeled COINTELPRO, including some that he himself had conceived and administered. These were intended to spread confusion and dissension among extremist political groups in this country, ranging from the Communist Party on the left to the Ku Klux Klan on the right. In 1975, he testified before the Senate Intelligence Committee, "Never once did I hear anybody, including myself raise the question, is this course of action which we have agreed upon lawful, is it legal, is it ethical or moral?"
Sullivan was instrumental in the arranging for the mailing of a tape recording in 1964 to Coretta Scott King, that contained secretly taped recordings of her husband Martin Luther King, Jr. speaking with other women. In a memo, Sullivan called King "a fraud, demagogue and scoundrel". He also gave orders to track down fugitive members of the Weather Underground in the early 1970s.
According to his autobiography, The Bureau: Thirty Years in Hoover's FBI, Sullivan admitted that he believed Martin Luther King Jr. to be the leader that his people needed. Sullivan was 100% for King because Sullivan saw in him an effective leader with much charisma, something the black people needed in their desire for civil rights. However, under Hoover's direction he was ordered to come up with evidence that proved King was embezzling or misusing large sums of money that contributed to the Soviet bloc of the Communist party. One of Hoover's main concerns during the 1960s was controlling the socialists who were accused of instigating a Communist revolution within the United States. Sullivan was forced to comply with Hoover and began tapping King's telephone in Atlanta.
After Hoover's death, Sullivan was brought back to office by President Richard Nixon. Sullivan hoped to replace Hoover as the bureau's director but was passed over by Richard Nixon in favor of loyalist L. Patrick Gray.