Túlio de Melo started his career with Atlético Mineiro, and moved to Europe in 2004 to join Danish top flight team Aalborg BK on loan. In 2005 he signed a three-year contract with French club Le Mans, where he gained a reputation as a powerful striker with the ability to lob keepers of international class from range. His impressive performances in the first half of the 2007–08 season (10 goals in 19 matches) caused interest from higher level teams, namely Serie A clubs Palermo and Parma. His name later caused controversy between these teams as it appeared he actually signed contracts with both clubs, but eventually it was Palermo who finalized his signing. Palermo paid the agent "SCMG Sport Consulting & Management Gmbh" €3.8 million to sign his outright.