The edges of black phosphorene (BP) have been extensively explored. The previous experimental observations that all the BP edges are semiconducting implies that the as-cut edges of BP tend to be reconstructed. Here we present a global structural search of three typical BP edges, namely armchair, zigzag and zigzag-1 edges. It is found that all the three pristine edges are metastable, and all of them can be quickly self-passivated by (i) forming P=P double bonds (one r and one p bond), (ii) reconstructing new polygonal rings will all P atoms bonded with three sp3 bonds or (iii) forming a special P(2)-P(4) configuration with a two-coordinated P atom accommodating two lone pair electrons and one four-coordinated P atom without lone pair electrons. Highly different from the pristine edges, all these highly stable reconstructed edges are semiconducting. This study showed that the reconstruction of the edges of a 2D material, just like the surfaces of a 3D crystal, must be considered for both fundamental studies and practical applications. Besides BP, this study also sheds light on the structures and properties of the edges of many other 2D materials.