LANGLEY, Va.— John Brennan is starting to tuck into breakfast, including black coffee and bacon, when he decides he hasn’t finished chewing on a rather tender subject for the director of the Central Intelligence Agency: politics.

“I am neither Democrat nor Republican nor ideological,” he told a Wall Street Journal reporter recently over a 7:15 a.m. meeting at CIA headquarters. “I’m an equal opportunity offender.”

Partly as a result, relations between the CIA and Congress are more fraught that at any point in the past decade. The source of the tension is the Senate intelligence committee’s classified report on the CIA’s controversial post-9/11 interrogation program—and the agency’s response to it.

The Short Answer

The bad blood could get worse in coming weeks, when portions of the report and CIA response are expected to be declassified. Mr. Brennan made it clear he had no plans to back down in the face of congressional criticism.

“When I speak about the report, I will probably annoy and alienate some people on both sides of this issue,” he said. “I will accept on behalf of the agency responsibility for failures, for problems and actions I believe should not have taken place. At the same time, I am going to take issue with some other elements of the report that I believe are inaccurate or misleading.”

His intention to push back could intensify strains with his natural allies as an Obama appointee—Democratic lawmakers. The ensuing fight could shape the agency’s long-term relationship with Congress, its public image and Mr. Brennan’s legacy at the CIA.

Relations between the CIA and Congress broke down on Jan. 15, when Mr. Brennan called a meeting on short notice with top lawmakers. Reading from notes and accompanied by the agency’s top lawyer, he alleged that aides from the Senate’s intelligence committee may have improperly obtained what he considered an off-limits CIA document, according to officials familiar with the meeting.

Sen. Dianne Feinstein, a California Democrat and chairman of the committee, was angry. The document was part of the committee’s investigation of the CIA interrogation program. Mr. Brennan’s investigation, she felt, was an affront to the Constitution’s separation of powers. She wanted an apology.

Senator Dianne Feinstein, shown in March, delivered a scathing critique of the CIA’s inquiry on the Senate floor. Bloomberg

Former Indiana Sen. Evan Bayh, a Democrat who sits on the CIA’s advisory board, recalls telling Mr. Brennan: “Sometimes you make a tactical retreat because it is the right thing to do.” Mr. Brennan has neither backed off nor apologized, and more than five months later, the standoff remains unresolved.

The CIA has churned through leaders roughly every couple of years since the 2001 terrorist attacks. Bolstering the agency’s relationship with Congress was a top priority for the Obama administration in 2009 when it installed former congressman Leon Panetta at the helm. Mr. Panetta’s open and personal approach gave him credibility with both Congress and his own employees.

Mr. Brennan, 58 years old and a 34-year veteran of U.S. spy services, was appointed to the top job in March 2013. He said little publicly during his first year on the job. His disdain of politics has made him popular at the CIA’s Langley, Va., headquarters, but less so with lawmakers, who hold the agency’s purse strings, can withhold authorization for spy operations around the world, and often serve as the CIA’s defender to the American public.

Soon after taking office, President Barack Obama officially ended the CIA’s “enhanced interrogation” program that permitted range of tactics, including waterboarding, which the president has characterized as torture.

Mr. Brennan agreed with the decision to end the program. The current fight is over how the history of that program will be written, and to what degree allegations of CIA mismanagement of parts of it will affect the agency’s operations today.

Critics, including members of the Senate panel, have long said the interrogation tactics were tantamount to torture, and ineffective. The CIA said the techniques weren’t torture and that the Justice Department signed off on them. While the agency acknowledges making mistakes carrying out the program, it said valuable information was produced.

Administration officials said that as public skepticism of U.S. counterterrorism programs and spy activity has grown, Mr. Brennan has gotten caught in the middle. “What he’s wrestling with is our country is changing off this permanent war footing,” said White House chief of staff Denis McDonough. The controversy over the Senate report, he said, “is a pretty good manifestation of how much the country is changing right now.”

The charged politics of the CIA’s interrogation program have dogged Mr. Brennan since 2008, when outcry from the political left prompted Mr. Brennan to withdraw his name from consideration to become his first CIA director. One reason for the political pushback: It wasn’t clear how loudly Mr. Brennan objected to the interrogation program at the time it was created in the wake of the 2001 attacks.

Mr. Brennan was a senior manager at CIA when the program began. He has said he opposed many of what the CIA called “enhanced interrogation techniques.”

Director of National Intelligence James Clapper said in an interview Mr. Brennan bowed out of the nomination process “prematurely” and that he could have weathered a confirmation battle. The job went to Mr. Panetta.

Instead, Mr. Brennan did a stint as White House counterterrorism chief. He was tapped again to be CIA director in January 2013. Lawmakers again raised questions about what involvement he had in the interrogation program’s inception, as well as about his central role in developing the administration’s program to target terrorists with drone strikes.

The Senate intelligence committee had spent three years investigating the interrogation techniques used on al Qaeda detainees. Sen. Mark Udall (D., Colo.) and others pressed Mr. Brennan to review the Senate report, which had been approved by the committee two months earlier but remained classified.

At his confirmation hearing, Mr. Brennan said the report raised questions about “a lot of the information that I was provided” about the interrogation program when he was in previous government posts. He also said, if confirmed, he planned to put his stamp on the CIA’s response before it was submitted to the Senate.

Several Democrats took that as a sign Mr. Brennan would be sympathetic to their criticism of the CIA’s handling of the program and the conclusion that it hadn’t been effective. “They had high expectations,” said one top Democratic congressional aide.

When he arrived at the CIA after his confirmation, Mr. Brennan read the report more thoroughly and solicited the views of agency officials, aides said. He said in the interview he concluded the report did show some CIA “shortcomings” and “failures,” but he also found fault with many of the report’s details and conclusions.

Mr. Brennan felt it was important to show he would stand behind the agency to correct facts when it came under political fire, a senior intelligence official said. That objective loomed larger when leaks from former National Security Agency contractor Edward Snowden put a greater spotlight on the intelligence world and sapped morale.

Last June 27, Mr. Brennan hand-delivered the CIA’s classified response to the Senate report to Sens. Feinstein and Saxby Chambliss (R., Ga.). Participants described the meeting as cordial.

Mr. Brennan’s focus at the time was on looming threats in Syria and Afghanistan, as well as a budget crunch and a need to close intelligence gaps, part of his back-to-basics strategic direction for the agency, according to the senior intelligence official.

His response to the Senate report bolstered his support inside the CIA, especially among officers initially skeptical of someone coming directly from the White House, former agency officials said. But it made relations with Congress more contentious.

In a bid to hash out differences between the report and the response, CIA and Senate staffers met 15 times over 60 hours. Although the Republicans had decided not to take part in the investigation, they joined the meetings. There were clashes between Democratic and Republican aides and tense exchanges with CIA officials.

At issue was what to conclude from the report’s facts. Some Senate aides argued that mistakes were symptoms of a larger problem at CIA. The agency contended they were isolated incidents and that the Senate report came to overly broad conclusions.

By the end of last summer, CIA staffers and lawmakers found some common ground. Some details of the report were changed, but the conclusions stayed the same.

Then lawmakers took a closer look at a document written under the agency’s previous director, which they called the “Panetta Review.” It included an assessment of the conclusions that could be drawn from documents the CIA provided the Senate. The CIA said it was a draft document prepared by some analysts without access to complete information, so didn’t reflect the agency’s position.

Sen. Ron Wyden, an Oregon Democrat and longtime committee member, said the apparent inconsistencies between the Panetta document and the CIA’s response to the Senate report showed it was “trying to sweep the mistakes of the past under the rug.”

The Senate committee asked the CIA for a copy of the Panetta document, but the agency declined. CIA officials came to believe that the committee already had obtained the draft document, which the CIA had considered outside the scope of what it had agreed to provide.

Suspicious that the draft had been improperly obtained, CIA officials reviewed computer usage to determine who had viewed it. The review turned up several Senate aides—a discovery that prompted the meeting between Mr. Brennan and top Senate Democrats in which the director said the Senate committee may have improperly gained access to the document. In dispute is whether the aides had a right to look at the document, and whether the CIA should have tracked computer usage.

The CIA’s top lawyer at the time, Robert Eatinger, later made a criminal referral on the matter to the Justice Department. Alarmed by Mr. Brennan’s accusations, Sen. Feinstein wrote to Mr. Brennan two days later, asking him to go no further. In another letter one week later, she asked a dozen questions about the CIA’s computer investigation and conveyed her concerns to the White House.

Senate Majority Leader Harry Reid (D., Nev.) urged Mr. Brennan to resolve the conflict before it became public, as did the White House. Mr. Brennan said he had been working with lawmakers to do just that. But media reports in March ended that possibility.

Ms. Feinstein took to the Senate floor to deliver an unusually scathing critique of the CIA’s inquiry, saying it may have violated the Constitution’s separation of powers and the Fourth Amendment protections against unreasonable searches.

Later that morning, Mr. Brennan defended the CIA at a long-scheduled event. “As far as the allegations of CIA hacking into Senate computers, nothing could be further from the truth,” he said.

Some of Mr. Brennan’s early supporters in Congress are critical of his handling of the issue.

“Being a good director also requires acknowledging mistakes and learning from them,” said Mr. Udall. “The CIA’s unauthorized search of the committee’s computers tells me that the CIA not only hasn’t learned from its mistakes, but continues to perpetuate them.”

Oregon’s Mr. Wyden said the CIA’s computer probe “has cast a large cloud over the agency and, in my view, significantly undermined their relationship with the Congress.” Sen. Martin Heinrich (D., N.M.), now says he regrets his vote to confirm Mr. Brennan.

Mr. Brennan is receiving quiet support from Republicans such as Sens. Saxby Chambliss (R., Ga.) and Richard Burr (R., N.C.), congressional aides and intelligence officials said. Every Republican member of the Senate intelligence panel declined to be interviewed for this article.

Mr. Bayh, the former senator, said that while congressional relations are important, being the CIA director of “is not a popularity contest.”

Mr. Brennan has been on Capitol Hill a number of times since the March fireworks. His exchanges with the intelligence committee have been professional, congressional aides said, but not friendly, and have had an “elephant-in-the-room” vibe.

While tempers have cooled in the past couple of months, the congressional aides said, the differences haven’t been resolved, and they expect tensions to intensify again when the report is finally made public.

“I believe that the public is going to be profoundly disturbed by this report,” said Mr. Wyden.

At the CIA, however, some officials believe the public will understand the agency’s actions when the report is declassified. “In the upper management ranks, no one is shaking in their boots,” said one former senior intelligence official.

In recent weeks, the CIA has begun to assume a more public profile, sponsoring a conference at Georgetown University and launching a Twitter account. Mr. Brennan is planning to mount an aggressive public defense of the agency, which could include speeches and media interviews.

“I’m going to get out more,” he said. “I think there are some important issues to be addressed. I have a responsibility to the agency, to the president and to the American people to make sure I speak up.”

Write to Siobhan Gorman at siobhan.gorman@wsj.com