In 1951 Gibson won her first international title, the Caribbean Championships in Jamaica, and later that year became one of the first Black competitors at Wimbledon, where she was defeated in the third round by Beverly Baker. In 1952 she was ranked seventh nationally by the USTA. In the spring of 1953 she graduated from Florida A&M and took a job teaching physical education at Lincoln University in Jefferson City, Missouri. During her two years at Lincoln she became romantically involved with an Army officer whom she never named publicly, and considered enlisting in the Women's Army Corps, but decided against it when the State Department sent her on a goodwill tour of Asia in 1955 to play exhibition matches with Ham Richardson, Bob Perry, and Karol Fageros. Many Asians in the countries they visited—Burma, Ceylon, India, Pakistan, and Thailand—"...felt an affinity to Althea as a woman of color and were delighted to see her as part of an official US delegation. With the United States grappling over the question of race, they turned to Althea for answers, or at least to get a firsthand perspective." Gibson, for her part, strengthened her confidence immeasurably during the six-week tour. When it was over, she remained abroad, winning 16 of 18 tournaments in Europe and Asia against many of the world's best players.