The spinor-helicity formalism has become an invaluable tool for understanding the S-matrix of massless particles in four dimensions. In this paper we construct a spinor-helicity formalism in six dimensions, and apply it to derive compact expressions for the three, four and five point tree amplitudes of Yang-Mills theory. Using the KLT relations, it is a straightforward process to obtain amplitudes in linearized gravity from these Yang-Mills amplitudes; we demonstrate this by writing down the gravitational three and four point amplitudes. Because there is no conserved helicity in six dimensions, these amplitudes describe the scattering of all possible polarization states (as well as Kaluza-Klein excitations) in four dimensions upon dimensional reduction. We also briefly discuss a convenient formulation of the BCFW recursion relations in higher dimensions.