A polynomial $f$ in non-commuting variables is trace-positive if the trace of $f(\underline{A})$ is positive for all tuples $\underline{A}$ of symmetric matrices of the same size. The investigation of trace-positive polynomials and of the question of when they can be written as a sum of hermitian squares and commutators of polynomials are motivated by their connection to two famous conjectures: The BMV conjecture from statistical quantum mechanics and the embedding conjecture of Alain Connes concerning von Neumann algebras. First, results on the question of when a trace-positive polynomial in two non-commuting variables can be written as a sum of hermitian squares and commutators are presented. For instance, any bivariate trace-positive polynomial of degree at most four has such a representation, whereas this is false in general if the degree is at least six. This is in perfect analogy to Hilbert's results from the commutative context. Further, a partial answer to the Lieb-Seiringer formulation of the BMV conjecture is given by presenting some concrete representations of the polynomials $S_{m,4}(X^2; Y^2)$ as a sum of hermitian squares and commutators. The second part of this work deals with the tracial moment problem. That is, how can one describe sequences of real numbers that are given by tracial moments of a probability measure on symmetric matrices of a fixed size. The truncated tracial moment problem, where one considers only finite sequences, as well as the tracial analog of the $K$-moment problem are also investigated. Several results from the classical moment problem in Functional Analysis can be transferred to this context. For instance, a tracial analog of Haviland's theorem holds: A traciallinear functional $L$ is given by the tracial moments of a positive Borel measure on symmetric matrices of a fixed size s if and only if $L$ takes only positive values on all polynomials which are trace-positive on all tuples of symmetric $s \times s$-matrices. This result uses tracial versions of the results of Fialkow and Nie on positive extensions of truncated sequences. Further, tracial analogs of results of Stochel and of Bayer and Teichmann are given. Defining a tracial Hankel matrix in analogy to the Hankel matrix in the classical moment problem, the results of Curto and Fialkow concerning sequences with Hankel matrices of finite rank or Hankel matrices of finite size which admit a flat extension also hold true in the tracial context. Finally, a relaxation for trace-minimization of polynomials using sums of hermitian squares and commutators is proposed. While this relaxation is not always exact, the tracial analogs of the results of Curto and Fialkow give a sufficient condition for the exactness of this relaxation.