Nelson Lisboa began playing basketball in the late 1940s when he joined Ginástico in Belo Horizonte. In his first year with the team Lisboa won the Minas Gerais youth championship, followed by two state championships with the senior team in 1956 and 1957. As the standout player on the team, he was selected as part of the Brazilian national team at the 1956 Melbourne Olympics. At the Games he played in four matches with Brazil eventually finishing sixth. A year after the Olympics, Lisboa also played with the national team at the Universiade in Paris.