Kingsville Mayor J. G. Goode, City Commissioners O. O. Hollingsworth and Gus Mecklin, and representatives of the Commercial Club, Al Kleberg and E. B. Erard, met with Mrs. Finnegan of the Women's Club. They accepted the architects' plan for a permanent library building to be constructed on the land donated by Mr. Kleberg and Mrs. King's estate.
The Austin architects Bertram E. Giesecke and August W. Harris had designed the plans for the library. The building was to be of Spanish mission style architecture, one story tall, of hollow tile and concrete construction, to complement nearby H. M. King School building. It would meet the needs of the library and the Women's Club for years to come, it was hoped, having a reading room, a small kitchenette for buffet luncheons, and a lobby. The commissioners decided to name it the Robert J. Kleberg Public Library.
The City of Kingsville advertised for sealed bids for constructing the building. The contract was awarded to E. E. McRoberts, who was low bidder with the price of $10,984.00. This included the one story stucco surfaced building, complete with water, wiring, and gas plumbing. Construction began in the last week of September, 1926, with the traditional ground breaking ceremony. Mrs. John D. Finnegan, representing the Women's Club, was given the privilege of lifting the first shovel of dirt. Work proceeded rapidly enough that by mid-November the walls of the building were partially completed. The Kingsville newspaper promised that when the grounds around the building were beautified, "the spot will be one of the show places of the city." By the first week in February, 1927, the building was completed except for a few finishing details of painting.