Nobody was better qualified for the task. He got his nickname, "Hashmark," because he had more hash marks (indicating enlistments) than chevrons (indicating rank) on his sleeve. He had enlisted in the Army in 1923, and again in 1926. He mustered out as a corporal, spent four years in civilian life, and then enlisted in the Naval Reserves and eventually in the regular Navy.
Not only was the Navy segregated, but it also restricted black Americans to service only in the Steward Branch. Six months before Pearl Harbor, while Johnson was serving aboard the U.S.S. Wyoming, on June 25, 1941, President Franklin D. Roosevelt signed Executive Order 8802. "I do hereby reaffirm the policy of the United States that there shall be no discrimination in the employment of workers in defense industries or government because of race, creed, color or national origin."
When Gilbert Johnson learned about Executive Order 8802, he requested immediate discharge from the Navy so he could enlist in the Marine Corps. His request was granted immediately. He had six years of Army experience in a combat unit, and nine years as a Navy Steward, when he joined the Marines.