By Godel's incompleteness theorem, if a formal axiomatic system capable of modeling arithmetic is consistent (i.e. free from contradictions), then there will exist statements that are true but whose truthfulness cannot be proven. Such statements are known as Godel statements.
So to answer your question... no, if a statement in mathematics is true, this does not necessarily mean there exists a proof to show it (of course, this assumes that mathematics is consistent, and that certainly appears to be the case). Hence, if the Collatz Conjecture was a Godel statement, then we would not be able to prove it - even if it was true.
Note that we could remedy this predicament by expanding the axioms of our system, but this would inevitably lead to another set of Godel statements that could not be proven.