Houston is often called “the Bayou City” because of its historic location on the Buffalo Bayou. Short-story writer O. Henry (1852-1910)—who lived in Texas as well as New York City—called New York “Bagdad-on-the-Subway” in the early 1900s, comparing the bustle of New York’s subways to the famed city.

Borrowing from O. Henry, legendary San Francisco columnist Herb Caen (1916-1997) called his city of San Francisco “Bagdad-by-the-Bay” by at least 1941.

There is no precise author or date for who and when the “Bayou City” was termed “Baghdad-on-the Bayou” (or “Bagdad-on-the Bayou"), but one citation occurs in 1939 and numerous citations occur in the early 1960s.

After the destruction caused by 2005’s Hurricane Katrina, the city of New Orleans was also nicknamed by some “Baghdad-on-the-Bayou.”


Wikipedia: Nicknames of Houston
Bayou City
Houston is known popularly as The Bayou City (and less frequently as “Baghdad on the Bayou") because it is home to ten winding waterways that flow through the surrounding area. Buffalo Bayou is the main waterway flowing through the city and has a significant place in Texas history, not only due to the founding place of the City of Houston, but also because the final battle for Texas Independence was fought along its banks.[5] Other major bayous in the city include White Oak Bayou, Brays Bayou and Sims Bayou.

Wikipedia: Buffalo Bayou
Buffalo Bayou is a main waterway flowing through Houston, Texas, USA. It begins on the west side of the city and flows east to the Houston Ship Channel. Along the way the bayou accents several major parks and numerous smaller neighborhood parks. The bayou is spring-fed and rises west of Houston near Katy, Texas.

History
The bayou has a significant place in Texas history, not only due to the founding place of the City of Houston, but also because the final battle for Texas Independence was fought along its banks where it merges with the San Jacinto River at the communities of Lynchburg and Harrisburg, near present day Deer Park, Texas.

The original Port of Houston was located at the confluence of Buffalo Bayou and White Oak Bayou in downtown Houston near the University of Houston-Downtown campus. This area is called “Allen’s Landing” and is now a park. It is the birthplace of the City of Houston.[2] Numerous historical sites, as well as ruins of old docks and facilities, can be seen along the banks of Buffalo Bayou.

Today, despite the urban environment, Buffalo Bayou and its parks remains the centerpiece for many festivals and gatherings in Houston throughout the year. It is also still very popular with canoe and kayak enthusiasts.

23 July 1939, New York Times, pg. BR3:
Houston was O. Henry’s Baghdad-on-the Bayou
(...)
In the years after he was fascinated by New York, and most of his best stories have the New York background, but it is plain now that Houston was the first real O. Henry “City”—the New York stories are deeply in debt to the early stimulus of the Houston streets. It was Baghdad-on-the-Bayou.

15 April 1962, Dallas Morning News, section 5, pg. 2:
HOUSTON, Texas—Bagdad-on-the-Bayou went Big League last week, and everyone seems to be pinching himself to see if it’s really true.

24 June 1963, Dallas Morning News, section 1, pg. 15:
HOUSTON, Texas—Baghdad on the Bayou, recipient of a multi-billion-dollar shot in the arm in the form of America’s first space city, resembled the Vegas strip last weekend.

Google Books
Police and Community Relations: A Sourcebook
by Arthur F. Brandstatter and Louis A Radelet
Glencoe Press
1968
Pg. 352:
Today, Houston has turned that muddy stream into a ship channel and become the second largest seaport in the nation. The superabundance of mineral resources in the area has made
this “Baghdad-on-the-Bayou.”

31 December 1968, Wall Street Journal, pg. 1, col. 4:
Actually, all of Houston—known as Baghdad on the Bayou and Space City U.S.A. --has been invited.

22 January 1970, Odessa American, pg. 3B, col. 1:
HOUSTON’S ROY HOFHEINZ has built an empire in the Bagdad on the Bayou.

19 March 1974, New York Times, “Houston—The President Is Coming, Ho-Hum, Ho-Hum” by Molly Ivins, pg. 37:
HOUSTON—President Nixon arrives today to visit “Baghdad on the Bayou” and there are a few billboards up around town that say, “Welcome to Houston, President Nixon.”