Coulomb gauge Yang-Mills theory within the first order formalism is considered with a view to deriving the propagator Dyson-Schwinger equations. The first order formalism is studied with special emphasis on the BRS invariance and it is found that there exists two forms of invariance - invariance under the standard BRS transform and under a second, non-standard transform. The field equations of motion and symmetries are derived explicitly and certain exact relations that simplify the formalism are presented. It is shown that the Ward-Takahashi identity arising from invariance under the non-standard part of the BRS transform is guaranteed by the functional equations of motion. The Feynman rules and the general decomposition of the two-point Green's functions are derived. The propagator Dyson-Schwinger equations are derived and certain aspects (energy independence of ghost Green's functions and the cancellation of energy divergences) are discussed.