Koutroulakis, the son of George and Eugenia Koutroulakis, was born at the South Highland Infirmary in Birmingham and grew up on Norwood Circle. He had one brother and two sisters. As a teenager Koutroulakis worked with his father at Derzis & Pappageorge Fruit Co. on Morris Avenue while he attended Phillips High School. Known as "Kouts" in school, he played basketball and ran track and also participated in R.O.T.C. with the rank of Cadet Staff Sergeant and in the Hi-Y club.
On January 18, 1948 shortly after he graduated from Phillips, Koutroulakis' father sent him to fill in for his vacationing uncle at the hot dog stand on 2nd Avenue North. Not long after returning from his trip to Greece, Pete suffered a heart attack and turned the business over to Gus.
Over the next 63 years, he hardly missed a day of work. He enlisted in the U.S. Army during the Korean War and was decorated for his combat service. He and his wife Kathy were married on January 10, 1986, after which he cut back on his hours at work. Later in life, he made two long trips to visit family in Greece, the last in 1995.
While his hot dogs were known for their special seasoned meat sauce, Gus himself was known for his encyclopedic memory of customer's orders, as well as for his gruff demeanor and fond ribbing of visitors. He considered retiring in 1998, complaining of sore feet, but decided to stay on to keep his mind active. He and his wife, Kathy, had no children. Koutroulakis died at his home in Homewood in April 2011. He is buried at Elmwood Cemetery.
- Evans, Amy. (March 2004) "Gus Koutroulakis. Interview for "Greeks in Birmingham". Southern Foodways Alliance Oral History Initiative - accessed March 26, 2006
- Robinson, Carol (April 6, 2011) "Beloved Birmingham hot dog man Constantine 'Gus' Koutroulakis, dies at 81." The Birmingham News
- "Constantine George 'Gus' Koutroulakis" obituary (April 7, 2011) The Birmingham News
- Taylor, Drew (July 21, 2021) "Memories of Pete’s Famous Hot Dogs owner ‘Gus’ Koutroulakis keep Birmingham legend alive" CBS42.com