At the headquarters of Southwest Airlines near the Dallas Love Field Airport, a large green sign with a big yellow arrow points to Bob Jordan’s office. It says “Bob’s Meet and Greet,” a folksy way to invite visitors to chat with the company’s chief executive.

Behind his desk are carefully ordered books, family photos and memorabilia, like model planes acquired over his 37 years at the airline.

Southwest, which first took flight in 1971, embraces its heritage. The headquarters are named after the airline’s iconoclastic co-founder, Herb Kelleher. There is a preserved replica of his office in the building. His quotes are painted on the wall.

So are some of Mr. Jordan’s. He is leaving his mark on the company in other ways, too, overseeing major changes to the way Southwest operates. The moves come after a battle with Elliott Investment Management, a hedge fund that called last year for Mr. Jordan’s ouster and criticized the airline for adhering to “antiquated business practices from decades ago.”

The changes include getting rid of Southwest’s quirky free-for-all boarding process, introducing premium-priced seats and, most controversially, ending its generous free bag policy for all fliers. When pressed on the timing and thinking behind the changes, Mr. Jordan described them as offering customers more choices.

Southwest expects to make roughly $4 billion in additional profit as a result. Its shares are up since it unveiled the new strategy, which settled the fight with Elliott.

But now, Mr. Jordan, 64, is trying to convince disgruntled customers that the airline is on the right path. Many say they feel it is ditching policies that have long set it apart from competitors. The heart in the company’s logo is a nod to the “love”-themed marketing in the airline’s earliest days, a legacy of Mr. Kelleher’s obsession with customer service, which also lives on in its stock ticker: LUV.

“Change is hard, and change is emotional,” Mr. Jordan said in a recent interview in his office. The needs of customers, employees and investors “don’t have to be at odds,” he added.

This interview has been edited and condensed for clarity.

How has it felt hearing from customers who don’t like the changes to bag fees or seating processes?

I know we have some that are not happy — and we have many, many, many that are happy.

You have to keep talking because sometimes people don’t understand what you’re doing. What I find is that once folks know where we’re headed, they’re very excited. I think you just have to play through this period of change because change is hard.

Our employees are excited about the changes. Because if you think about it, if in the open-seating world a family gets on and they can’t sit together, the flight attendant is having to police that in the cabin. Our open-seat boarding can cause a lot of pre-boards, and our agents are having to police that. You have people who paid for early boarding, and then we have more pre-boards than anybody else. So folks that paid for earlier boarding are going, “Well, wait, why?”

The decision in March to scrap your ‘Bags Fly Free’ policy caused a lot of consternation, and months earlier you had said you weren’t going to touch that. Can you walk me through the thinking?

Customers today want a lot of choice, especially coming out of the pandemic. The customer’s needs and wants are just different.

If you don’t follow your customers, you look up one day and your products just aren’t attractive any longer. The move to bag fees is really about choice.

If you look on the website today, we have a wider variety of products, including this new basic fare that comes with a lot of restrictions. For just a few more dollars, you can buy up to the next fare, and it has fewer restrictions.

Did you think about rolling out these changes more gradually?

The core of Southwest is still really different. But what you saw is that other airlines went through these changes over a decade or more. There is a bit of catch-up here because we’re moving to that world, but in months, not a decade.

It may feel really fast because there’s a bit of catch-up here, but it’s going really, really well.

A lot of the changes reward frequent fliers. But is Southwest de-emphasizing price-sensitive people who don’t travel as much?

We’re not abandoning anybody. You are going to get great fares on Southwest Airlines, period.

My whole point is there’s more coming to the strategy as we keep evolving, but it’s all about staying true to who we are — best people, best hospitality, best service — while stretching the model to meet the needs of our customers.

You say “no” to too many things, and when you look up years later, you become irrelevant to a lot of folks. We’re just not going to do that.

So, why now? Last year, the hedge fund Elliott pushed hard for changes. Was that the driving force, ultimately?

I’ve been asked a lot about Elliott and what went on last summer. We had an investor day on Sept. 26 where we laid out assigned seating, extra leg room and a number of things. All of that strategy was well underway, way ahead of Elliott.

So that was not driven by Elliott. They are a large shareholder, but they’re one out of many.

What did you learn about yourself as a leader during the fight last year?

Actually, this may sound strange: I enjoy periods that are crazy like that because you learn and you’re moving. You’re working on a problem. I love problem solving.

I’ve heard people say, “Hey, you’re a lot more command-and-control today.” They don’t mean that in a negative way. What they mean is, “You’re faster to decide what we’re going do and move on.”

You started at Southwest back in 1988, when Herb Kelleher, a co-founder, was still running the company.

I met Herb on my first day.

And it was a smaller company then.

Seven thousand people, I think. What we did in revenue in the year when I was hired, I believe we do in five days now.

Wow. What do you think Herb would make of the changes to the airline he built?

One of the No. 1 Herb quotes was, “If you don’t change, you die.”

Herb didn’t build the airline to be about open seating and plastic boarding cards. That was an outgrowth of wanting to be efficient. Herb built the airline around being different from a service perspective.

What’s funny is that Herb would say: “We’re never going to change boarding. We are never going to go into a big airport like LaGuardia. We’re never going to have a frequent-flier program.” And then we would do it.

Let’s zoom out. There’s a lot of uncertainty about the economy with tariffs and the state of the consumer. Is it harder to make decisions right now?

The macro effects are real. There is absolutely an impact. We saw a drop in early February, another drop in demand in March and another one in April. Bookings are stable today, but they are stable at a lower rate. There’s no doubt consumers have done what they often do: When uncertainty hits, they can turn spending off pretty quickly.

How are you seeing consumer behavior change?

People are waiting to make decisions. This is a generality, but the summer would never be on sale like it is today. You’re seeing airlines with a lot of sale fares, and that’s very unusual because in the summer, the demand is strong. It does tell you people are waiting until they’re closer to their intended trip.

So, what do you think will define this summer travel season?

I think this summer will be defined generally as demand did not come in as strong as we all thought six months ago.

You see weakness all over the place.

OK, let’s time travel some. Where did you grow up?

Indiana, but then did high school in Houston and went to Texas A&M.

What did your parents do?

My mom’s a homemaker, and my dad’s a civil engineer.

What did you want to do when you grew up?

Some kind of engineer or scientist. At one point, I wanted to be an astronaut. I loved the whole space thing. This was in the ’60s.

I ultimately got a degree in computer science and an M.B.A.

Speaking of computers, how is Southwest using artificial intelligence?

We think that charging for bags will decrease the number of checked bags. That’s great, because checked bags have weight and they take handling. We think it will modestly increase the number of bags that have to be checked at the gate. So you’re going to run out of bin space, and you don’t want that to occur in the cabin. The worst thing is if you’ve already boarded, and now somebody says: “Hey, I need your bag. There’s no more space.” You want to handle that at the gate.

By using A.I. and data around flights, the agents now have a tool on their device that predicts the number of gate-checked bags. The tool has been very accurate.

Time for the lightning round. You run an airline, so I want to know your plane habits. What’s your advice for jet lag?

Stay up. I don’t really get jet lagged.

Where’s your favorite place to sit on a plane?

Window. But for business, I sit in the aisle because I like to get up, talk to the flight attendants. I serve snacks. I pick up trash. Then I go sit in the cockpit and talk to our pilots.

I don’t want to be crawling over people, so I tend to sit on the aisle so I can get out and do stuff.

What’s your go-to plane attire?

I don’t wear a suit much. If I’m going to D.C. to meet with a senator or something, I’m obviously going to have a suit on. But typically, it’s a vest or a polo because I want to work with our crew.

I want to go downstairs and unload bags. It’s super hard to unload bags and get in the belly of the aircraft with a suit on.

How often do you check your stock price?

I watch it constantly. Daily.

How do you sign off your emails?

Luv, Bob.