Current cost estimation methods for early mission formulation typically use parametric regressions and analogies based on historical data sets. This approach, while widely spread in industry, is also subject to critique due to large parameter uncertainty and due to the reliance on small data sets on which regressions are based. Issues are accentuated in early mission formulation efforts, due to the immaturity of the mission concept and technical data available in preliminary design phases. In other words, conventional cost estimation methods sometimes have too high ambitions for the quantity of the information available in early mission formulation. Yet, cost estimation is of primary importance to determine feasibility of a mission within a space program. In this paper, we explore less ambitious approaches based on machine learning algorithms that are better suited to cost estimation for early mission formulation. In particular, we use classification algorithms to categorize missions into a predefined number of cost classes, e.g. Discovery or Flagship mission class. We compare different classification algorithms, study the performance and the utility of different levels of granularity in class definition, and test the proposed approaches on selected Earth Observation missions for which public information on cost is available. The methodology proposed in this paper provides an alternative approach for early cost estimation of new missions to cost and systems engineers.