It is not yet entirely clear whether Mars began as a warm and wet planet that evolved towards the present-day cold and dry body or if it always was cold and dry with just some sporadic episodes of liquid water on its surface. An important clue into this question can be gained by studying the earliest evolution of the Martian atmosphere and whether it was dense and stable to maintain a warm and wet climate or tenuous and susceptible to strong atmospheric escape. We discuss relevant aspects for the evolution and stability of a potential early Martian atmosphere. This contains the solar EUV flux evolution, the formation timescale and volatile inventory of the planet including volcanic degassing, impact delivery and removal, the loss of a catastrophically outgassed steam atmosphere, atmosphere-surface interactions, and thermal and non-thermal escape processes affecting any secondary atmosphere. While early non-thermal escape at Mars before 4 billion years ago (Ga) is poorly understood, particularly in view of its ancient intrinsic magnetic field, research on thermal escape processes indicate that volatile delivery and volcanic degassing cannot counterbalance the strong thermal escape. Therefore, a catastrophically outgassed steam atmosphere of several bars of CO2 and H2O, or CO and H2 for reduced conditions, could have been lost within just a few million years (Myr). Thereafter, Mars likely could not build up a dense secondary atmosphere during its first ~400 Myr but might only have possessed an atmosphere sporadically during events of strong volcanic degassing, potentially also including SO2. This indicates that before ~4.1 Ga Mars indeed might have been cold and dry. A denser CO2- or CO-dominated atmosphere, however, might have built up afterwards but must have been lost later-on due to non-thermal escape processes and sequestration into the ground.