Interview of Hillary Clinton in Egypt: "PROGRESS", as seen by Madame Clinton.

This is a rush transcript from "On the Record," June 4 - 5, 2009. This copy may not be in its final form and may be updated.

MARTHA MACCALLUM, FOX NEWS GUEST HOST: And after much anticipation, President Obama made his speech to the Muslim world in Cairo, Egypt, today. He wasn't the only one in the Middle East. Secretary of State Hillary Clinton went along for the trip, and our own Greta Van Susteren was there, as well. Secretary Clinton went "On the Record" with Greta in Cairo.

GRETA VAN SUSTEREN, FOX NEWS HOST: Madam Secretary, nice to see you.

HILLARY CLINTON, SECRETARY OF STATE: Very good to see you, Greta.

VAN SUSTEREN: Now, I don't want to make it a pop quiz, but I'm just curious. Since January, how many countries have you visited, any idea?

CLINTON: You know, I could stop and count, but I've been all over the world on behalf of our new administration and President Obama and our country. It has been the most extraordinary honor to go from Latin America to Asia, representing American values and interests.

VAN SUSTEREN: Obviously, here in Cairo, Egypt, and the -- it must be particularly important to the administration because not just the president of the United States but the secretary of state is here, as well. Why did you both come?

CLINTON: Because this is a very important part of our new diplomacy, our outreach, our policy of engagement and partnership. This is something the president promised to do early on in his term. And it is my second trip to Egypt since I've been secretary of state.

I came and was at Sharm el-Sheikh for an important conference. And it is really critical that we make clear, as the president did in this magnificent speech he gave, that we want to work with people all over the world, regardless of religion -- we have, you know, no feeling of hostility or conflict with Muslims everywhere, we have very specific principles and values that we believe in, which the president outlined today -- because we're looking for ways to solve problems and promote progress and prosperity with people of good faith. [ I guess that does not include religious Jews in Israel, but it DOES include Muslims/ terrorists, DS]

And I thought that it was important that we all be here to send a strong signal that America is doing what the president said we would do in his inaugural address, you know, he'll stretch out his hand, and hopefully, people will unclench their fists.

VAN SUSTEREN: Well, it seemed to me in listening to the speech -- I think the president said that the point of the speech was sort of to reboot America's relationship with the Muslim world. But it seemed to me that all roads lead back to the Israeli-Palestinian conflict, that if -- you know, if that could be resolved, it would certainly go far towards solving lot of the other problems in the area. Am I right?

CLINTON: I think, as the president pointed out in his speech, that is certainly a very important part of our relationships with people all over, in particular Arab countries, majority Muslim countries.

But extremism exists apart from that. Democracy and human rights need to be pursued in spite of that. Women's rights have to be elevated and respected. Economic opportunity has to be made broadly available. The threat of nuclear proliferation is a threat to people of all faiths, in every corner of the world.

So it is an important part of what we have to work on, and the president and I have been very engaged in that from the beginning. But he wanted to put it rightly in a broader context, which is important because we don't want people saying, Well, if only that issue were resolved, then everything would be fine. That is not the case. There are other, you know, concerns that we have to be honest in addressing, and I think the president did an excellent job in setting those forth.

VAN SUSTEREN: But if we -- if that one doesn't get addressed -- and I don't know that it can -- I mean, certainly, many administrations have tried it. It may be sort of the problem that can't be solved. I know everyone valiantly tries to solve it from the United States. But if that one can't be solved, you've got so many other sort of companion issues.

CLINTON: Well, yes, and that's why we're working on all of them. I mean, we're going forward as early in this administration as we possibly can. It's why I recommended appointing special envoys. But we know that there are independent sources of challenge.

The threat of Iran having a nuclear weapon is one that has to be addressed with the same high-level priority. The problem of extremism in Afghanistan and Pakistan has to be put on the front burner.

So we're not elevating one of these issues over the other. We are addressing all of them because they are interconnected, and that was part of the point the president was making.

VAN SUSTEREN: It was sort of interesting listening to the audience, though, is that there were -- there was a lot of applause when he mentioned something like, you know, no more settlements or anything that was favorable to the Palestinians.

And then when he said things like, you know, You can't threaten -- it's wrong to threaten Israel, or you know, that there are Holocaust deniers and things like that, there were no applause lines. I realize we're in Egypt, but it was -- it seemed like sort of a -- this is sort of a friendly environment for Israel and the United States and the Palestinians. I thought that was unusual.

CLINTON: But you know, Greta, what was so important about the president's speech is that that is a speech that he could give anywhere. It will be read by, I would bet, hundreds of millions of people in the next weeks and months.

And it was, as he said, the truth as he saw it, obviously, from an American perspective but nevertheless, one that has, you know, basis in evidence and history. And I think the fact that he came here and talked about everything -- of course, there was going to be some greater reaction to parts of it because it was familiar terrain. But he planted seeds. He encouraged people to have to have a conversation and to think hard about their perspectives and points of view.

I think he also challenged Americans, you know? He went right at how we can't have stereotypes for other people, as we don't want to have stereotypes about us. This was a speech that I believe will be viewed historically as a very significant turning point.

You know, one of the most important points that he made was how, if the Palestinians had pursued a different path of non-violence, of you know, following an example of a Gandhi or a Dr. Martin Luther King, who knows where we'd be right now, that violence is not the answer. It does not change hearts and minds, it hardens them.

I don't know whether people who have such a different perspective will hear that and think to themselves, Well, you know, there's something there that I should perhaps ponder. But without saying it, without offering the challenge in such an eloquent and reasoned way, one thing I know for sure is that nobody will have that conversation. And I think it will happen now.

VAN SUSTEREN: Well, and I agree that the speech was eloquent, and I - - you know, I think more than anything, we all would like to see all the principles laid out, the democracy, women's right. But the thing that sort of stuck me is that he said very -- and he's said it before -- no more settlements. And at the same time, I know that Netanyahu is talking about sort of natural growth, which doesn't mean no more settlements.

So now here's -- here we're saying, This is not going to happen, but in fact, it is happening, you know, unless you say natural growth construction is not new settlements.

CLINTON: Well, we're at the very beginning of this effort. I think it is important for the president to set forth his concerns about the Israelis and the Palestinians because he made it very clear, no more incitement against Israel, security, not violence, to set that out as part as what we have directed George Mitchell to do, which is to get in depth with both sides, really not just the Israelis and the Palestinians, but also the Arabs, and to say very clearly, Here's what the United States believes is in the best interests of the Israelis and the Palestinians.

We know we can't get there by imposing such an ending. That's not our position or role. But we want to be as clear in our description of what we think will lead to a more peaceful and secure future for Israel and for the Palestinians.

And then we have to work with the parties. Now, we've made progress over the past, you know, 30, 35 years. We've really seen progress. You know, who would have thought that Egypt and Israel would have ever made a peace, Israel and Jordan, that certain concessions would have been made by successive Israeli governments, regardless of their political parties. So I think the president, as he said, is patient.

You know, we're starting early because we know what a hard road we're asking people to travel. But that patience, that persistence and perseverance that he and I feel toward this very difficult challenge means that we are going to keep saying what we believe and we're going to keep working with those who have to make the decisions.